题解 P4215 【踩气球】

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:$

#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;
}