CF: 368 (Div. 2) [ 2D-Persistance Segmenttree ]

CF: 368 (Div. 2) [ 2D-Persistance Segmenttree ]

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  Digit     0123456789012345678 ///
#define MX     100002
#define inf    2000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

struct room { ///For Shelf_BookRoom
    int l,r,sm,f;
    room() {};
};

struct data {///For Shelf
    int l,r,rm;
    data() {};
};


int nw,pt,n,m,fl,x,y,tot,tg;
data nd[(20*MX)+5];
room T[(20*MX)+5];

int go(int idx,int l,int r) { ///Toggle
    int id=++pt;
    T[ id ]=T[ idx ];
    T[ id ].f^=1;
    T[ id ].sm=(r-l+1)-T[id].sm;
    return id;
}

int Upds(int pn,int l,int r,int p) {
    int id=++pt;
    T[ id ]=T[ pn ];
    if( l==r ) {
        T[ id ].sm=fl;
        return id;
    }
    int md=(l+r)>>1;
    if( T[id].f ) {
        T[id].l=go(T[id].l,l,md);
        T[id].r=go(T[id].r,md+1,r);
        T[id].f=0;
    }
    if( p<=md )T[id].l=Upds( T[id].l,l,md,p );
    else T[id].r=Upds( T[id].r,md+1,r,p );

    T[ id ].sm=( T[ T[id].l ].sm+T[ T[id].r ].sm );

    return id;
}

int Build(int l,int r) {
    int id=++nw;
    if( l==r ) {
        nd[id].rm=++pt;
        return id;
    }
    int md=(l+r)>>1;
    nd[id].l=Build(l,md);
    nd[id].r=Build(md+1,r);
    return id;
}

int Upd(int pn,int l,int r,int p) {
    int id=++nw;
    nd[ id ]=nd[ pn ];
    if( l==r ) {
        int xx;
        if(tg)xx=nd[id].rm=go( nd[id].rm,1,m );
        else xx=nd[id].rm=Upds( nd[id].rm,1,m,y );
        tot=T[ xx ].sm;
        return id;
    }
    int md=(l+r)>>1;
    if(p<=md)nd[id].l=Upd(nd[id].l,l,md,p);
    else nd[id].r=Upd(nd[id].r,md+1,r,p);
    return id;
}

struct Data { ///Summation in BIT+Sum at Pos
    int l,r,sm;
    Data() {};
};

Data Nd[(20*MX)+2];
int Nw,Root[MX+2];

int Ins(int pn,int l,int r,int p,int v) {
    int id=++Nw;
    Nd[ id ]=Nd[ pn ];
    if( l==r ) {
        Nd[ id ].sm+=v;
        return id;
    }
    int md=(l+r)>>1;
    if( p<=md ) Nd[id].l=Ins(Nd[id].l,l,md,p,v);
    else Nd[id].r=Ins( Nd[id].r,md+1,r,p,v );
    Nd[ id ].sm=( Nd[ Nd[id].l ].sm+Nd[ Nd[id].r ].sm );
    return id;
}

int QrySm(int nn,int l,int r,int p) {
    if( l==r ) return Nd[nn].sm;
    int md=(l+r)>>1;
    if( p<=md ) return QrySm( Nd[nn].l,l,md,p );
    else QrySm( Nd[nn].r,md+1,r,p );
}

int root[MX+2];

int main() {
    int i,k,op,q;
    S2(n,m);
    S(q);
    nw=1;
    Nw=1;
    root[0]=Build(1,n);
    Root[0]=Nw;
    for(i=1; i<=q; i++) {
        root[i]=root[i-1];
        Root[i]=Root[i-1];
        S(op);
        if(op==4) { ///Roll back time machine;
            S(k);
            root[i]=root[k];
            Root[i]=Root[k];

        } else if( op==1 ) {  ///add bag at bookSelf;
            S2(x,y);
            fl=1;
            root[i]=Upd(root[i],1,n,x);
            int xx=QrySm(Root[i],1,n,x);
            Root[i]=Ins(Root[i],1,n,x,tot-xx);

        } else if( op==2 ) { ///remove
            S2(x,y);
            fl=0;
            root[i]=Upd(root[i],1,n,x);
            int xx=QrySm(Root[i],1,n,x);
            Root[i]=Ins(Root[i],1,n,x,tot-xx);

        } else {
            S(x);
            tg=1; ///Toggle
            root[i]=Upd(root[i],1,n,x);
            int xx=QrySm(Root[i],1,n,x);
            Root[i]=Ins(Root[i],1,n,x,tot-xx);
            tg=0;
        }
        printf("%d\n",Nd[ Root[i] ].sm);
    }
    return 0;
}