BZOJ 3211: 花神游历各国

正文索引 [隐藏]

Description

Input

Output

每次x=1时,每行一个整数,表示这次旅行的开心度

Sample Input

4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4

Sample Output

101
11
11

HINT

对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9

题解

这里的修改只有sqrt是吧。那么一个数一直sqrt就变成1了,那么之后就不用对它进行修改操作了!所以我们记录一个区间最大值,如果最大值大于1我们才修改这个区间。
P.S. 一开始看错题了,以为这题要动态修改+Sqrt 求区间最大连续子区间最大和QuQ 最近脑子不太好= =

代码