【Luogu】P1383高级打字机

可持久化线段树模板题之一。

权当温习主席树模板

#include<cstdio>

#include<cstdlib>

#include<cctype>

#define left (rt<<1)

#define right (rt<<1|1)

#define mid ((l+r)>>1)

#define lson l,mid,left

#define rson mid+1,r,right

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int root[];

int ls[];

int rs[];

char tree[];

int len[];

int ID;

void add(int l,int r,int &rt,char x,int pos,int last){

    rt=++ID;

    if(l==r){

        tree[rt]=x;

        return;

    }

    ls[rt]=ls[last];

    rs[rt]=rs[last];

    if(pos<=mid)    add(l,mid,ls[rt],x,pos,ls[last]);

    else             add(mid+,r,rs[rt],x,pos,rs[last]);

}

int query(int pos,int l,int r,int rt){

    if(l==r)    return rt;

    if(pos<=mid)    return query(pos,l,mid,ls[rt]);

    else             return query(pos,mid+,r,rs[rt]);

}

int now;

int main(){

    int n=read();

    for(int i=;i<=n;++i){

        char ch[];int x;

        scanf("%s",ch);

        if(ch[]=='Q'){

            x=read();

            int pos=query(x,,n,root[now]);

            printf("%c\n",tree[pos]);

        }

        else if(ch[]=='U'){

            x=read();

            now++;

            len[now]=len[now-x-];

            root[now]=root[now-x-];

        }

        else{

            char c[];

            scanf("%s",c);

            now++;len[now]=len[now-]+;

            add(,n,root[now],c[],len[now],root[now-]);

        }

    }

    return ;

}