BZOJ 4631: 踩气球 线段树+vector

对于每个节点开一个 vector 就好了. 

code: 

#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

#define N 100006
#define lson now<<1
#define rson now<<1|1

using namespace std;

namespace IO {

    void setIO(string s)
    {
        string in=s+".in";
        string out=s+".out";
        freopen(in.c_str(),"r",stdin);
        // freopen(out.c_str(),"w",stdout);
    }

};

int ans;

int sum[N],A[N];

struct node {
    int sum;
    vector<int>v;
}s[N<<2];

void push(int l,int r,int now,int L,int R,int p)
{
    if(l>=L&&r<=R)
    {
        ++sum[p];
        s[now].v.push_back(p);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)  push(l,mid,lson,L,R,p);
    if(R>mid)   push(mid+1,r,rson,L,R,p);
}

void build(int l,int r,int now)
{
    if(l==r)
    {
        s[now].sum=A[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,lson);
    build(mid+1,r,rson);
    s[now].sum=s[lson].sum+s[rson].sum;
}

void update(int l,int r,int now,int p)
{
    --s[now].sum;
    if(!s[now].sum)
    {
        for(int i=0;i<s[now].v.size();++i)
        {
            --sum[s[now].v[i]];
            if(!sum[s[now].v[i]]) ++ans;
        }
    }
    if(l==r) return;
    int mid=(l+r)>>1;
    if(p<=mid)  update(l,mid,lson,p);
    else update(mid+1,r,rson,p);
}

int main()
{
    // IO::setIO("input");
    int i,j,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)  scanf("%d",&A[i]);
    build(1,n,1);
    for(i=1;i<=m;++i)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        push(1,n,1,l,r,i);
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int x;
        scanf("%d",&x);
        x=(x+ans-1)%n+1;
        update(1,n,1,x);
        printf("%d\n",ans);
    }
    return 0;
}