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

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

@krydom10月前

10/15
08:43
线段树

[bzoj 3211] 花神游历各国

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

 116

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

25

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

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

由于一个数经过很少次开平方操作就会变成0或者1,那么就可以如果一段区间内所有数都是0或者1的话就不再进行修改操作,然后线段树上搞搞就好了

c++:

pascal:

 

[bzoj 3211] 花神游历各国