d801: SCOI2006 2.动态最值(minmax)
Tags :
Accepted rate : 37人/50人 ( 74% ) [非即時]
評分方式:
Tolerant

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

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

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

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

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


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」