题目概述

Luogu3835

解题报告

由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。

未解之谜：Split肯定需要新建节点，但是Merge好像并不需要？洛谷这题实测Merge不新建节点也不会访问到任何一个旧节点。但是为了保险，下面的代码会检测是否访问到了旧节点，如果访问到了就新建。

示例程序

#include<cstdio>
#include<random>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=500000,maxt=3e7,MAXINT=2147483647;

int te;
struct NODE {NODE* son[2];int si,val,fix;} 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=x;pl->fix=mrand();
    return pl;
}
void Pushup(ptr p) {p->si=p->son[0]->si+1+p->son[1]->si;}
ppp Split(ptr p,int k){
    if (p==PL) return mp(PL,PL);
    ptr now=++pl;
    *now=*p;
    ppp res;
    if (k<p->val){
        res=Split(p->son[0],k);
        now->son[0]=res.sc;
        res.sc=now;
    } else {
        res=Split(p->son[1],k);
        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;
        now->son[1]=Merge(x->son[1],y);
    } else {
        if (y<=lim) now=++pl,*now=*y; else now=y;
        now->son[0]=Merge(x,y->son[0]);
    }
    Pushup(now);
    return now;
}
int getrk(ptr p,int k){
    if (p==PL) return 0;
    return p->val<k?getrk(p->son[1],k)+p->son[0]->si+1:getrk(p->son[0],k);
}
int getkth(ptr p,int k){
    if (p==PL) return 0;
    if (k==p->son[0]->si+1) return p->val;
    return k<=p->son[0]->si?getkth(p->son[0],k):getkth(p->son[1],k-p->son[0]->si-1);
}
int getpre(ptr p,int k){
    if (p==PL) return -MAXINT;
    return p->val<k?max(getpre(p->son[1],k),p->val):getpre(p->son[0],k);
}
int getsuf(ptr p,int k){
    if (p==PL) return MAXINT;
    return p->val>k?min(getsuf(p->son[0],k),p->val):getsuf(p->son[1],k);
}
ptr Insert(ptr p,int k){
    lim=pl;
    ppp res=Split(p,k);
    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(Merge(B.fr,Merge(B.sc->son[0],B.sc->son[1])),A.sc);
}
int main(){
    PL->son[0]=PL->son[1]=PL;
    ro[0]=PL;
    readi(te);
    for (int t=1,fa,tp,x;t<=te;t++){
        readi(fa);readi(tp);readi(x);
        ro[t]=ro[fa];
        if (tp==1) ro[t]=Insert(ro[fa],x); else
        if (tp==2) ro[t]=Delete(ro[fa],x); else
        if (tp==3) writei(getrk(ro[t],x)+1); else
        if (tp==4) writei(getkth(ro[t],x)); else
        if (tp==5) writei(getpre(ro[t],x)); else
        if (tp==6) writei(getsuf(ro[t],x));
    }
    return 0;
}