【题解】洛谷1198 [JSOI2008]最大数

2017-12-28 21:21:34


分块/线段树/单调栈……各种方法随便搞。。。

当然我线段树不想敲,单调栈不会,于是就选择了分块。。。

易见,数列最多有200000个数,于是分成448块,每块447个数。。。

然后把belong和左右界处理出来。

对于Q操作,和一般分块是一样的。

对于A操作,长度加一后放入值,然后更新该块的最大值。

代码见蒟蒻的blog