「BZOJ3339」Rmq Problem

2014年5月17日5,5731

Description

Input

Output

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

题解

这一题在线似乎比较麻烦

至于离线。。

首先按照左端点将询问排序

然后一般可以这样考虑

首先如何得到1-i的sg值呢

这个可以一开始扫一遍完成

接着考虑l-r和l+1-r的答案有何不同

显然是l-next[l]-1这一段所有sg值大于a[l]的变为a[l]

这一步如果暴力修改的话只有30分

但是修改区间我们可以想到线段树,这样就能a了

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
PKUSC2015 命运下的蝼蚁?|杂文|HZWER:We are OIers Recent comment authors
  Subscribe  
提醒
trackback

[…] 本弱上去讲个mex,刷刷存在感,结果上台就不知道自己口胡什么鬼了,我错了大家没听懂不要打我,可以看看http://hzwer.com/3032.html […]