[bzoj 4631] step on the balloon (link list + line tree combination)

Conveyor biu~
First, the original sequence is chained together with a linked list. Each time the value of a point is reduced to 0, the point is deleted from the linked list. That is to use the chain list to maintain the first point whose value is not 0.
For each point in the sequence, a weight line segment tree with value range [1,n] is opened. For each bear child interval [l,r], l is added to the line tree r as the weight. When the value of point x is reduced to 0 and will be deleted from the list, assuming that the first point on the left side of point x is not 0, then the weight of every > p on the line tree x, that is, every bear child interval, will become happy after the value of point x is reduced to 0. Then we can delete all the weights greater than p on point x from the line tree and update the answer with them, and then merge line tree x into line tree p.

#include<bits/stdc++.h>
#define N 100005
using namespace std;
struct Node{
    Node *ch[2];
    int sum;
    Node(){
        ch[0]=ch[1]=0x0;
        sum=0;
    }
    inline void maintain(){
        sum=0;
        if(ch[0])   sum+=ch[0]->sum;
        if(ch[1])   sum+=ch[1]->sum;
    }
}*root[N]={new Node};
int n,m,q,ans,a[N],pre[N],nex[N];
void add(Node *&o,int l,int r,int x){
    if(!o)  o=new Node;
    if(l==r){
        ++o->sum;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)  add(o->ch[0],l,mid,x);
    else    add(o->ch[1],mid+1,r,x);
    o->maintain();
}
void del(Node *&o,int l,int r,int x){
    if(!o || !o->sum)   return;
    if(l>=x){
        ans+=o->sum;
        o=0x0;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)  del(o->ch[0],l,mid,x);
    del(o->ch[1],mid+1,r,x);
    o->maintain();
}
void Merge(Node *&a,Node *b,int l,int r){
    if(!b)  return;
    if(!a)  {a=b;return;}
    int mid=l+r>>1;
    a->sum+=b->sum;
    Merge(a->ch[0],b->ch[0],l,mid);
    Merge(a->ch[1],b->ch[1],mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        pre[i]=i-1,nex[i]=i+1;
        root[i]=new Node;
    }
    for(int i=1;i<=m;++i){
        int l,r;
        scanf("%d%d",&l,&r);
        add(root[r],1,n,l);
    }
    scanf("%d",&q);
    while(q--){
        int x;
        scanf("%d",&x);
        x=(x+ans-1)%n+1;
        if(!--a[x]){
            int p=pre[x];
            pre[nex[x]]=pre[x];
            nex[pre[x]]=nex[x];
            del(root[x],1,n,p+1);
            Merge(root[p],root[x],1,n);
        }
        printf("%d\n",ans);
    }
    return 0;
} 

Posted on Mon, 30 Mar 2020 11:32:50 -0700 by iconicCreator