首页 > 代码库 > bzoj 4631: 踩气球 线段树合并
bzoj 4631: 踩气球 线段树合并
4631: 踩气球
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 265 Solved: 136
[Submit][Status][Discuss]
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
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]中的气球已经全部被踩爆）。
1
1
2
3
【样例说明】
实际上每次操作的盒子是： 4 2 1 3 5
在第二次操作后，第二个熊孩子会高兴 （区间[2,2]中的气球已经全部被踩爆）。
在第四次操作后，第三个熊孩子会高兴（区间[1,3]中的气球已经全部被踩爆）。
在第五次操作后，第一个熊孩子会高兴（区间[5,5]中的气球已经全部被踩爆）。
这题好像怎么做都行，于是我写了一发线段树合并。
维护n棵权值线段树，把每个区间以左端点为值插入右端点代表的线段树中。
再用个并查集维护每个点前第一个没被踩完的盒子$f[i]$。
每次踩空一个盒子i，找到$f[i]$，把$i$这棵线段树中大于$f[i]$的点删掉，再把$i$合并到$f[i]$上。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define N 100005 6 using namespace std; 7 int n,m; 8 int c[N],now; 9 struct node 10 { 11 int l,r,sum; 12 }a[N*20];int cnt; 13 void add(int x,int l,int r,int z) 14 { 15 if(l==r) 16 { 17 a[x].sum++; 18 return ; 19 } 20 int mid=(l+r)>>1; 21 if(z<=mid) 22 { 23 if(!a[x].l)a[x].l=++cnt; 24 add(a[x].l,l,mid,z); 25 } 26 else 27 { 28 if(!a[x].r)a[x].r=++cnt; 29 add(a[x].r,mid+1,r,z); 30 } 31 a[x].sum=a[a[x].l].sum+a[a[x].r].sum; 32 return ; 33 } 34 int f[N]; 35 int find(int x) 36 { 37 if(f[x]==x)return x; 38 return f[x]=find(f[x]); 39 } 40 int la=0; 41 int root[N]; 42 void del(int x,int l,int r,int z) 43 { 44 if(l==r) 45 { 46 la+=a[x].sum; 47 a[x].sum=0; 48 return ; 49 } 50 int mid=(l+r)>>1; 51 if(z<=mid) 52 { 53 if(a[a[x].l].sum)del(a[x].l,l,mid,z); 54 } 55 if(a[a[x].r].sum)del(a[x].r,mid+1,r,z); 56 a[x].sum=a[a[x].l].sum+a[a[x].r].sum; 57 return ; 58 } 59 void merge(int x,int y,int l,int r) 60 { 61 if(l==r) 62 { 63 a[x].sum+=a[y].sum; 64 return ; 65 } 66 int mid=(l+r)>>1; 67 if(a[x].l) 68 { 69 if(a[y].l)merge(a[x].l,a[y].l,l,mid); 70 } 71 else a[x].l=a[y].l; 72 if(a[x].r) 73 { 74 if(a[y].r)merge(a[x].r,a[y].r,mid+1,r); 75 } 76 else a[x].r=a[y].r; 77 a[x].sum=a[a[x].r].sum+a[a[x].l].sum; 78 return ; 79 } 80 int main() 81 { 82 scanf("%d%d",&n,&m); 83 for(int i=1;i<=n;i++)scanf("%d",&c[i]); 84 for(int i=0;i<=n;i++)root[i]=++cnt; 85 for(int i=1;i<=n;i++)f[i]=i; 86 int t1,t2; 87 for(int i=1;i<=m;i++) 88 { 89 scanf("%d%d",&t1,&t2); 90 add(root[t2],1,n,t1); 91 } 92 int q;scanf("%d",&q); 93 94 for(int i=1;i<=q;i++) 95 { 96 scanf("%d",&t1); 97 t1=(t1-1+la)%n+1; 98 c[t1]--; 99 if(c[t1]==0)100 {101 f[t1]=t1-1;102 int aa=find(t1);103 del(root[t1],1,n,aa+1);104 merge(root[aa],root[t1],1,n);105 }106 printf("%d\n",la);107 }108 return 0;109 }
bzoj 4631: 踩气球 线段树合并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。