【BZOJ 4631】4631: 踩气球 （线段树）

时间：2023-12-14 20:28:38

4631: 踩气球

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 316  Solved: 153

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

Source

【分析】

　　　我觉得这个跟扫描线的线段树维护是有异曲同工之妙的。

　　 把线段树上覆盖熊孩子区间的点标记。当这个点全部被清0的时候让cnt--，当熊孩子的log个区间减剩0，ans++。

　　看代码易懂。

　　【可以思考一下操作变成区间的时候怎么办

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 2000010

 #define INF 0xfffffff

 #define LL long long

 int a[Maxn];

 struct node

 {

     int l,r,lc,rc;

 }tr[Maxn*];

 int tot;

 LL sm[Maxn],ss[Maxn];

 int build(int l,int r)

 {

     int x=++tot;

     tr[x].l=l;tr[x].r=r;

     ss[x]=sm[r]-sm[l-];

     if(l<r)

     {

         int mid=(l+r)>>;

         tr[x].lc=build(l,mid);

         tr[x].rc=build(mid+,r);

     }

     else tr[x].lc=tr[x].rc=;

     return x;

 }

 int first[Maxn],nt[Maxn],cnt[Maxn],tto[Maxn];

 int len;

 void add(int x,int id)

 {

     tto[++len]=id;nt[len]=first[x];first[x]=len;cnt[id]++;

 }

 void ins(int x,int l,int r,int id)

 {

     if(tr[x].l==l&&tr[x].r==r)

     {

         add(x,id);return;

     }

     int mid=(tr[x].l+tr[x].r)>>;

     if(r<=mid) ins(tr[x].lc,l,r,id);

     else if(l>mid) ins(tr[x].rc,l,r,id);

     else {ins(tr[x].lc,l,mid,id);ins(tr[x].rc,mid+,r,id);}

 }

 int ans;

 void solve(int x)

 {

     for(int i=first[x];i;i=nt[i])

     {

         int y=tto[i];

         cnt[y]--;

         if(cnt[y]==) ans++;

     }

 }

 void change(int x,int y)

 {

     ss[x]--;

     if(ss[x]==) solve(x);

     if(tr[x].l==tr[x].r) return;

     int mid=(tr[x].l+tr[x].r)>>;

     if(y<=mid) change(tr[x].lc,y);

     else change(tr[x].rc,y);

 }

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     sm[]=;

     for(int i=;i<=n;i++) sm[i]=sm[i-]+a[i];

     build(,n);

     memset(first,,sizeof(first));

     for(int i=;i<=m;i++)

     {

         int l,r;

         scanf("%d%d",&l,&r);

         ins(,l,r,i);

     }

     int q;

     scanf("%d",&q);

     for(int i=;i<=q;i++)

     {

         int x;scanf("%d",&x);

         x=(x+ans-)%n+;

         change(,x);

         printf("%d\n",ans);

     }

     return ;

 }

2017-04-10 14:37:10

相关文章