Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom9月前

10/15
15:27
线段树

[bzoj 3339] Rmq Problem

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

1

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

2-1

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

3-1

♦♦♦♦♦♦   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   ♦♦♦♦♦♦

6

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

先按照左端点将询问排序,得到1-i的sg值可以一开始扫一遍完成,接着考虑l-r和l+1-r的答案有何不同,显然是l-next[l]-1这一段所有sg值大于a[l]的变为a[l],用线段树维护一下就可以了

c++:

pascal:

 

[bzoj 3339] Rmq Problem