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

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

@krydom1年前

07/1
16:38
线段树

[bzoj 4631] 踩气球

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

六一儿童节到了, SHUXK 被迫陪着M个熊孩子玩一个无聊的游戏:有N个盒子从左到右排成一排,第i个盒子里装着Ai个气球。
SHUXK 要进行Q次操作,每次从某一个盒子里拿出一个没被踩爆的气球,然后熊孩子们就会立刻把它踩爆。
这M个熊孩子每个人都指定了一个盒子区间[Li, Ri]。 如果某一个时刻,一个熊孩子发现自己选定的盒子区间[Li, Ri]中的所
有气球都已经被踩爆了,他就会非常高兴(显然之后他一直会很高兴)。
为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望, SHUXK 想向你询问:
他每次操作过后会有多少个熊孩子很高兴。

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

第一行包含两个正整数N和M,分别表示盒子和熊孩子的个数。
第二行包含N个正整数Ai( 1 < = Ai < = 10^5),表示每个盒子里气球的数量。
以下M行每行包含两个正整数Li, Ri( 1 < = Li < = Ri < = N),分别表示每一个熊孩子指定的区间。
以下一行包含一个正整数Q,表示 SHUXK 操作的次数。
以下Q行每行包含一个正整数X,表示这次操作是从第X个盒子里拿气球。为
了体现在线,我们对输入的X进行了加密。
假设输入的正整数是x',那么真正的X = (x' + Lastans − 1)Mod N + 1。其
中Lastans为上一次询问的答案。对于第一个询问, Lastans = 0。
输入数据保证1 < = x' < = 10^9, 且第X个盒子中有尚未被踩爆的气球。
N < = 10^5 ,M < = 10^5 �,Q < = 10^5

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

包含Q行,每行输出一个整数,表示 SHUXK 一次操作后询问的
答案。答案的顺序应与输入数据的顺序保持一致。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

0
1
1
2
3
【样例说明】
实际上每次操作的盒子是: 4 2 1 3 5
在第二次操作后,第二个熊孩子会高兴 (区间[2,2]中的气球已经全部被踩爆)。
在第四次操作后,第三个熊孩子会高兴(区间[1,3]中的气球已经全部被踩爆)。
在第五次操作后,第一个熊孩子会高兴(区间[5,5]中的气球已经全部被踩爆)。

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

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

直接建一颗线段树,那么一个孩子一定对应着至多log n个线段树上的区间,当且仅当这些区间的和都是0时,这个熊孩子才会感到很高兴,直接做就行了

 

[bzoj 4631] 踩气球