题
题
Splay 裸题 拿非旋treap维护
建树勉强卡过去 下次要写建树QAQ
1507:

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
char val[1024*2048+100];
int size[1024*2048+100],lson[1024*2048+100],rson[1024*2048+100],key[1024*2048+100];
int root,tot;
int lazy[1024*2048+100];
void update(int x)
{
    size[x]=size[lson[x]]+size[rson[x]]+1;
    return ;
}
void pushdown(int x)
{
    if(lazy[x]) 
    {
        swap(lson[x],rson[x]);
        if(lson[x]) lazy[lson[x]]^=1;
        if(rson[x]) lazy[rson[x]]^=1;
        lazy[x]=0;
    }
    return ;
}
int merge(int x,int y)
{
    pushdown(x),pushdown(y);
    if(x==0||y==0) return x|y;
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),update(x);
    return x;
}
par split(int x,int k)
{
    if(k==0) return make_pair(0,x);
    pushdown(x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x);
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x);
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,update(x);
        return make_pair(x,t.second);
    }
}
int now;
char s[100];
void output(int x)
{
    if(!x) return ;
    output(lson[x]);
    printf("%c",val[x]);
    output(rson[x]);
}
int main()
{
    scanf("%d",&n);
    for(int x,i=1;i<=n;i++)
    {
        scanf("%s",s);
        if(s[0]=='M') scanf("%d",&now);
        else if(s[0]=='I') 
        {
            scanf("%d",&x);
            par t1;
            t1=split(root,now);
            char c=getchar();
            int xx=x;
            while(xx)
            {
                if(c!='\n') 
                {
                    size[++tot]=1,key[tot]=rand(),val[tot]=c;
                    t1.first=merge(t1.first,tot);
                    xx--;
                }
                c=getchar();
            }
            root=merge(t1.first,t1.second);
        }
        else if(s[0]=='D')
        {
            scanf("%d",&x);
            par t1,t2;
            t2=split(root,now+x);
            t1=split(t2.first,now);
            root=merge(t1.first,t2.second);
        }
        else if(s[0]=='G')
        {
            scanf("%d",&x);
            par t1,t2;
            t2=split(root,now+x);
            t1=split(t2.first,now);
            output(t1.second);
            printf("\n");
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[0]=='P') now--;
        else if(s[0]=='N') now++;
    }
    return 0;
}

1269:

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
char val[1024*2048+100];
int size[1024*2048+100],lson[1024*2048+100],rson[1024*2048+100],key[1024*2048+100];
int root,tot;
int lazy[1024*2048+100];
void update(int x)
{
    size[x]=size[lson[x]]+size[rson[x]]+1;
    return ;
}
void pushdown(int x)
{
    if(lazy[x]) 
    {
        swap(lson[x],rson[x]);
        if(lson[x]) lazy[lson[x]]^=1;
        if(rson[x]) lazy[rson[x]]^=1;
        lazy[x]=0;
    }
    return ;
}
int merge(int x,int y)
{
    pushdown(x),pushdown(y);
    if(x==0||y==0) return x|y;
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),update(x);
    return x;
}
par split(int x,int k)
{
    if(k==0) return make_pair(0,x);
    pushdown(x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x);
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x);
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,update(x);
        return make_pair(x,t.second);
    }
}
int now;
char s[100];
int main()
{
    scanf("%d",&n);
    for(int x,i=1;i<=n;i++)
    {
        scanf("%s",s);
        if(s[0]=='M') scanf("%d",&now);
        else if(s[0]=='I') 
        {
            scanf("%d",&x);
            par t1;
            t1=split(root,now);
            char c=getchar();    
            while(c>126||c<32) c=getchar();
            while(c>=32&&c<=126)
            {
                size[++tot]=1,key[tot]=rand(),val[tot]=c;
                t1.first=merge(t1.first,tot);
                c=getchar();
            }
            root=merge(t1.first,t1.second);
        }
        else if(s[0]=='D')
        {
            scanf("%d",&x);
            par t1,t2;
            t2=split(root,now+x);
            t1=split(t2.first,now);
            root=merge(t1.first,t2.second);
        }
        else if(s[0]=='R')
        {
            scanf("%d",&x);
            par t1,t2;
            t2=split(root,now+x);
            t1=split(t2.first,now);
            lazy[t1.second]^=1;
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[0]=='G')
        {
            par t1,t2;
            t2=split(root,now+1);
            t1=split(t2.first,now);
            printf("%c\n",val[t1.second]);
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[0]=='P') now--;
        else if(s[0]=='N') now++;
    }
    return 0;
}