d801. SCOI2006 2.动态最值(minmax)
標籤 :
通過比率 : 56人/75人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:47

內容
有一个包含n个元素的数组,要求实现以下操作:DELETE k删除位置k上的数。右边的数往左移一个位置。QUERY i j查询位置i~j上所有数的最小值和最大值。例如有10个元素:
位置12345678910
元素1526749315
QUERY 2 8的结果为2 9。依次执行DELETE 3和DELETE 6(注意这时删除的是原始数组的元素7)后数组变为:
位置12345678
元素15674315
QUERY 2 8的结果为1 7。
輸入說明
第一行包含两个数n, m,表示原始数组的元素个数和操作的个数。第二行包括n个数,表示原始数组。以下m行,每行格式为1 k或者2 i j,其中第一个数为1表示删除操作,为2表示询问操作。
輸出說明
对每个询问操作输出一行,包括两个数,表示该范围内的最小值和最大值。
範例輸入 #1
10 4
1 5 2 6 7 4 9 3 1 5
2 2 8
1 3
1 6
2 2 8
範例輸出 #1
2 9
1 7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 5.0s , <50M
提示 :

50%的数据满足1<=n, m<=104,删除操作不超过100个100%的数据满足1<=n, m<=106, 1<=m<=106对于所有的数据,数组中的元素绝对值均不超过109

//这题是SCOI(四川)2006的第二题,时间限制是每组测试数据5s,还是遵循原来的限制吧,不过时间有点紧。
//由于原测试数据一共有10组,这里只取最大的那一组。

標籤:
出處:
SCOI2006第二题 [管理者: liouzhou_101 (王启圣) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
19584 ntnuapcs1936 (ntnuapcs1936) d801
線段樹*2
902 2019-10-11 18:59