题解 P4215 【踩气球】
Forever_Pursuit
2020-01-20 16:08:06
**题意：**
给定一个长度为 $N$ 的序列和 $M$ 个区间，进行 $Q$ 次单点修改操作，每次操作后询问 $M$ 个区间中有多少个区间内的数全为 $0$ 。
**转化：**
题中保证了所有数非负，所以只要一个区间的和为 $0$ ，那么这个区间内的数就全为 $0$ 。
可以用线段树维护区间和与单点修改。
对于每一个区间，我们可以把它拆成线段树上的一些节点，如果拆成了 $s$ 个节点，每当其中的一个节点的值变为 $0$ 时，将 $s$ 减 $1$ ，当 $s$ 变为 $0$ 时，输出的答案就应该加 $1$ 。
时间复杂度为 $O((m+q)logn+n)$ 。
**实现：**
对于线段树上的每一个节点，使用一个 $vector$ 数组来保存有哪些区间在拆开后的节点中包含了这个节点，在单点修改操作时，若一个节点的值变为 $0$ 时，就将保存的所有区间的 $s$ (该区间拆成的节点数)减 $1$ ，同时更新值为 $0$ 的 $s$ 的数量(即要输出的答案)。
$code:$
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define N 100005
struct node1{
int val;
vector<int>vp;
}t[N<<2];
struct node2{
int l,r,s;
}k[N];
int n,m,q,a[N],op,x,ans;
void build(int p,int l,int r){
if(l==r){
t[p].val=a[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build((p<<1)+1,mid+1,r);
t[p].val=t[p<<1].val+t[(p<<1)+1].val;
}
void update(int p,int x,int v,int l,int r){
if(l==r){
t[p].val+=v;
if(t[p].val==0){
for(int i=0;i<t[p].vp.size();i++){
k[t[p].vp[i]].s--;
if(k[t[p].vp[i]].s==0)ans++;
}
}
return;
}
int mid=(l+r)>>1;
if(x<=mid)update(p<<1,x,v,l,mid);
else update((p<<1)+1,x,v,mid+1,r);
t[p].val=t[p<<1].val+t[(p<<1)+1].val;
if(t[p].val==0){
for(int i=0;i<t[p].vp.size();i++){
k[t[p].vp[i]].s--;
if(k[t[p].vp[i]].s==0)ans++;
}
}
}
void split(int p,int x,int y,int l,int r,int i){
if(x<=l&&y>=r){
t[p].vp.push_back(i);
k[i].s++;
return;
}
int mid=(l+r)>>1;
if(x<=mid)split(p<<1,x,y,l,mid,i);
if(y>mid)split((p<<1)+1,x,y,mid+1,r,i);
}
void init(){
scanf("%d%d",&n,&m);
for(rint i=1;i<=n;i++)
scanf("%d",&a[i]);
for(rint i=1;i<=m;i++)
scanf("%d%d",&k[i].l,&k[i].r);
scanf("%d",&q);
build(1,1,n);
for(rint i=1;i<=m;i++)
split(1,k[i].l,k[i].r,1,n,i);
}
int main(){
init();
while(q--){
scanf("%d%",&x);
x=(x+ans-1)%n+1;
update(1,x,-1,1,n);
printf("%d\n",ans);
}
return 0;
}
```