题目概述

Luogu5055

解题报告

带tag的可持久化平衡树，Pushdown需要在新建的节点上进行，并且Pushdown需要新建两个儿子，以避免影响之前的信息。

好像看到了很多Pushdown在原节点上进行的代码（但不是即时交换儿子），由于个人习惯是传tag必须保证节点已更新，所以没有采用这种方法。

示例程序

#include<cstdio>
#include<random>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=3e7;

int te;LL lstans;
struct NODE {NODE* son[2];int si,val,fix;LL sum;bool flip;} PL[maxt+5];
typedef NODE* ptr;typedef pair<ptr,ptr> ppp;
ptr pl=PL,ro[maxn+5],lim;
mt19937 mrand(19260817);

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[1<<16],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[1<<16];
    fastO() {si=0;}
    void putc(char ch){
        if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
#define putc fo.putc
template<typename T> void writei(T x,char ch='\n'){
    static int len=0,buf[100];
    if (x<0) putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) putc(buf[--len]+48);
    if (ch) putc(ch);
}
inline ptr newnode(int x){
    pl++;pl->son[0]=pl->son[1]=PL;
    pl->si=1;pl->val=pl->sum=x;pl->fix=mrand();
    pl->flip=0;
    return pl;
}
void Pushup(ptr p){
    p->si=p->son[0]->si+1+p->son[1]->si;
    p->sum=p->son[0]->sum+p->val+p->son[1]->sum;
}
ptr Addflip(ptr p){
    if (p==PL) return PL;
    ptr now=++pl;*now=*p;
    swap(now->son[0],now->son[1]);
    now->flip^=1;
    return now;
}
void Pushdown(ptr p){
    if (p->flip){
        p->son[0]=Addflip(p->son[0]);
        p->son[1]=Addflip(p->son[1]);
        p->flip^=1;
    }
}
ppp Split(ptr p,int k){
    if (p==PL) return mp(PL,PL);
    ptr now=++pl;*now=*p;
    Pushdown(now);
    ppp res;
    if (k<=now->son[0]->si){
        res=Split(now->son[0],k);
        now->son[0]=res.sc;
        res.sc=now;
    } else {
        res=Split(now->son[1],k-now->son[0]->si-1);
        now->son[1]=res.fr;
        res.fr=now;
    }
    Pushup(now);
    return res;
}
ptr Merge(ptr x,ptr y){
    if (x==PL || y==PL) return x==PL?y:x;
    ptr now;
    if (x->fix<y->fix){
        if (x<=lim) now=++pl,*now=*x; else now=x;
        Pushdown(now);
        now->son[1]=Merge(now->son[1],y);
    } else {
        if (y<=lim) now=++pl,*now=*y; else now=y;
        Pushdown(now);
        now->son[0]=Merge(x,now->son[0]);
    }
    Pushup(now);
    return now;
}
ptr Flip(ptr p,int L,int R){
    lim=pl;
    ppp A=Split(p,L-1),B=Split(A.sc,R-L+1);
    return Merge(A.fr,Merge(Addflip(B.fr),B.sc));
}
ptr Insert(ptr p,int rk,int k){
    lim=pl;
    ppp res=Split(p,rk);
    return Merge(Merge(res.fr,newnode(k)),res.sc);
}
ptr Delete(ptr p,int k){
    lim=pl;
    ppp A=Split(p,k),B=Split(A.fr,k-1);
    return Merge(B.fr,A.sc);
}
LL getsum(ptr p,int L,int R){
    lim=pl;
    ppp A=Split(p,L-1),B=Split(A.sc,R-L+1);
    pl=lim;
    return B.fr->sum;
}
int main(){
    PL->son[0]=PL->son[1]=PL;
    ro[0]=PL;
    readi(te);
    for (int t=1,fa,tp,x,y;t<=te;t++){
        readi(fa);readi(tp);readi(x);x^=lstans;
        if (tp!=2) readi(y),y^=lstans;
        ro[t]=ro[fa];
        if (tp==1) ro[t]=Insert(ro[fa],x,y); else
        if (tp==2) ro[t]=Delete(ro[fa],x); else
        if (tp==3) ro[t]=Flip(ro[fa],x,y); else
        if (tp==4) writei(lstans=getsum(ro[t],x,y));
    }
    return 0;
}