NEUACM代码库/数据结构/伸展树

来自NEUACM WIKI
跳转到: 导航, 搜索

介绍

竞赛时,很多时候用到的树形结构。

代码很长。具体请找度娘。

例题有

HDU 1890

HDU 3436

HDU 3487

HDU 4441


BZOJ 1861

代码

//
//  1890.cpp
//  ACM_HDU
//
//  Created by ipqhjjybj on 13-8-27.
//  Copyright (c) 2013年 ipqhjjybj. All rights reserved.
//  参考着别人Ac代码敲的
//
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
struct SplayTree{
    const static int maxn=111111;
    int n,tot,root;
    map<int,int> Map;
    int child[maxn][2];
    int pre[maxn],size[maxn],flex[maxn];
    int id[maxn];
    struct node{
        int id,val;
        bool operator < (const node & tmp) const{
            return val<tmp.val||(val==tmp.val&&id<tmp.id);
        }
    }in[maxn];
    void Pushup(int &x){
        size[x]=size[child[x][0]]+size[child[x][1]]+1;
    }
    void Pushdown(int &x){
        if(flex[x]){
            flex[x]=0;
            flex[child[x][0]]^=1;
            flex[child[x][1]]^=1;
            swap(child[x][0],child[x][1]);
        }
    }
    void Del_root(){
        int t=root;
        if(child[root][1]){
            root=child[root][1];
            Select(1,0);
            child[root][0]=child[t][0];
            if(child[t][0]) pre[child[t][0]]=root;
        }else
            root=child[root][0];
        pre[root]=0;
        Pushup(root);
    }
    // c==0  左旋 ,  c==1 右旋
    inline void Rotate(int x, int c) {    // 旋转, c=0 左旋, c=1 右旋
        int y = pre[x];
        Pushdown(y);
        Pushdown(x);
        child[y][!c] = child[x][c];
        if ( child[x][c] )    pre[ child[x][c] ] = y;
        pre[x] = pre[y];
        if ( pre[y] )    child[ pre[y] ][ child[pre[y]][1] == y ] = x;
        child[x][c] = y;
        pre[y] = x;
        Pushup(y);
    }
    void Splay(int x,int f){
       // puts("fuck Splay");
        Pushdown(x);
        while(pre[x]!=f){
        //    printf("f=%d pre[%d]=%d\n",f,x,pre[x]);
            int y=pre[x],z=pre[y];
            Pushdown(z),Pushdown(y),Pushdown(x);
            if(pre[pre[x]]==f){
                Rotate(x,child[pre[x]][0]==x);
            }else{
                if ( child[z][0] == y ) {
                    if ( child[y][0] == x )
                        Rotate(y, 1), Rotate(x, 1);
                    else
                        Rotate(x, 0), Rotate(x, 1);
                }
                else {
                    if ( child[y][0] == x )
                        Rotate(x, 1), Rotate(x, 0);
                    else
                        Rotate(y, 0), Rotate(x, 0);
                }
            }
        }
        Pushup(x);
        if(f==0) root=x;
    }
    void Select(int k,int f){
        int x=root;
        while(1){
            Pushdown(x);
            if(k==size[child[x][0]]+1)
                break;
            if(k<=size[child[x][0]])
                x=child[x][0];
            else{
                k-=size[child[x][0]]+1;
                x=child[x][1];
            }
        }
        Splay(x,f);
    }
    void Newnode(int &x,int f){
        //puts("fuck newnode");
        x=++tot;
        child[x][0]=child[x][1]=0;
        pre[x]=f;
        flex[x]=0;
        size[x]=1;
    }
    void Build(int &x,int l,int r,int f){
        if(l>r)return;
        int mid=(l+r)>>1;
        //puts("Fuck(Build)");
        Newnode(x,f);
        Map[id[mid]]=x;
        Build(child[x][0],l,mid-1,x);
        Build(child[x][1],mid+1,r,x);
        Pushup(x);
    }
    void init(int _n){
        n=_n; Map.clear(); root=tot=0;
        pre[0]=child[0][0]=child[0][1]=0;
        size[0]=flex[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&in[i].val);
            in[i].id=i;
        }
        sort(in+1,in+1+n);
        for(int i=1;i<=n;i++)
            id[in[i].id]=i;
        Map[id[1]]=1;
        Map[id[n]]=2;
        Newnode(root,0);
        Newnode(child[root][1],root);
        Build(child[child[root][1]][0],2,n-1,child[root][1]);
        Pushup(child[root][1]);
        Pushup(root);
    }
    void solve(int n){
        for(int i=1;i<=n;i++){
            //printf("i=%d\n",i);
            //printf("Map[%d]=%d\n",i,Map[i]);
            Splay(Map[i],0);
            //printf("root=%d\n",root);
            printf("%d%c",i+size[child[root][0]],i==n?'\n':' ');
            flex[child[root][0]]^=1;
            Del_root();
        }
    }
}spt;
int main(){
    int n;
    while(scanf("%d",&n)&&n){
        if(n==1){scanf("%*d");puts("1");continue;}
        spt.init(n);
        spt.solve(n);
    }
    return 0;
}
//
//  3487.cpp
//  ACM_HDU
//
//  Created by ipqhjjybj on 13-9-6.
//  Copyright (c) 2013年 ipqhjjybj. All rights reserved.
//  先看完别人代码。后来凭记忆敲的Ac代码
//
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#define N 300015
#define inf 1<<29
#define MOD 100000007
#define LL long long
#define _match(a,b) ((a)==(b))
 
#define Key_value ch[ch[root][1]][0]
 
using namespace std;
int n,q;
int size[N],pre[N],key[N],num[N],rev[N];
int ch[N][2],tot,root,node[N];
void Push_Up(int &t){
    size[t]=size[ch[t][0]]+size[ch[t][1]]+1;
}
void Push_Down(int &t){
    if(rev[t]){
        swap(ch[t][0],ch[t][1]);
        rev[ch[t][0]]^=1;
        rev[ch[t][1]]^=1;
        rev[t]=0;
    }
}
void NewNode(int &t,int k,int father){
    t=++tot;
    pre[t]=father;
    key[t]=k;
    rev[t]=0;
    ch[t][0]=ch[t][1]=0;
}
void Build(int &t,int l,int r,int father){
    if(l>r)return;
    int mid=(l+r)>>1;
    NewNode(t,mid,father);
    Build(ch[t][0],l,mid-1,t);
    Build(ch[t][1],mid+1,r,t);
    Push_Up(t);
}
void Init(){
    root=tot=0;
    ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=0;
    NewNode(root,-1,0);
    NewNode(ch[root][1],-1,root);
    size[root]=2;
    Build(Key_value,1,n,ch[root][1]);
    Push_Up(ch[root][1]);
    Push_Up(root);
}
void Rotate(int x,int c){ // c==0左旋,c==1右旋
    int y=pre[x];
    Push_Down(y);
    Push_Down(x);
    ch[y][!c]=ch[x][c];
    pre[ch[x][c]]=y;
    if(pre[y])
        ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][c]=y;
    pre[y]=x;
    Push_Up(y);
}
void Splay(int x,int father){
    Push_Down(x);
    while(pre[x]!=father){
        int y=pre[x],z=pre[y];
        Push_Down(z),Push_Down(y),Push_Down(z);
        if(pre[y]==father){
            Rotate(x,ch[y][0]==x);
        }else{
            if(ch[z][0]==y){
                if(ch[y][0]==x)
                    Rotate(y,1),Rotate(x,1);
                else Rotate(x,0),Rotate(x,1);
            }else{
                if(ch[y][0]==x)
                    Rotate(x,1),Rotate(x,0);
                else Rotate(y,0),Rotate(x,0);
            }
        }
    }
    Push_Up(x);
    if(father==0) root=x;
}
int Get_Kth(int t,int k){
    Push_Down(t);
    if(size[ch[t][0]]==k-1)
        return t;
    else if(size[ch[t][0]]>=k)
        return Get_Kth(ch[t][0],k);
    else return Get_Kth(ch[t][1],k-size[ch[t][0]]-1);
}
int Min_Value(int t){
    Push_Down(t);
    while(ch[t][0]){
        t=ch[t][0];
        Push_Down(t);
    }
    return t;
}
void Reversal(int a,int b){
    a=Get_Kth(root,a);
    b=Get_Kth(root,b+2);
    Splay(a,0);
    Splay(b,root);
    rev[Key_value]^=1;
}
void Cut(int a,int b,int c){
    int x=Get_Kth(root,a);
    int y=Get_Kth(root,b+2);
    Splay(x,0);
    Splay(y,root);
    int tmp=Key_value;
    Key_value=0;
    Push_Up(ch[root][1]);
    Push_Up(root);
    int cm=Get_Kth(root,c+1);
    Splay(cm,0);
    int mi=Min_Value(ch[root][1]);
    Splay(mi,root);
    Key_value=tmp;
    pre[Key_value]=ch[root][1];
    Push_Up(ch[root][1]);
    Push_Up(root);
}
int cnt;
void InOrder(int r){
    if(r==0)
        return;
    Push_Down(r);
    InOrder(ch[r][0]);
    if(cnt>=1&&cnt<=n){
        if(cnt>1)printf(" ");
        printf("%d",key[r]);
    }
    cnt++;
    InOrder(ch[r][1]);
}
int main(){
    while(scanf("%d%d",&n,&q)!=EOF){
		if(n==-1&&q==-1)
			break;
		Init();
		while(q--){
			char str[10];
			int a,b,c;
			scanf("%s",str);
			if(str[0]=='C'){
				scanf("%d%d%d",&a,&b,&c);
				Cut(a,b,c);
			}
			else{
				scanf("%d%d",&a,&b);
				Reversal(a,b);
			}
		}
		cnt=0;
		InOrder(root);
		printf("\n");
	}
	return 0;
}
//
//  3436.cpp
//  ACM_HDU
//
//  Created by ipqhjjybj on 13-9-7.
//  Copyright (c) 2013年 ipqhjjybj. All rights reserved.
//  先看完别人代码的。。
//
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 222222;
int n,q,k,N;
char re[MAXN];
int req[MAXN],a[MAXN],na,beg[MAXN],end[MAXN];
int num[MAXN],pre[MAXN],ch[MAXN][2],root;
void flow(int x){
    num[x]=num[ch[x][0]]+num[ch[x][1]]+end[x]-beg[x]+1;
}
inline void rotate(int n)
{
    int t=pre[n];
    bool isr=(ch[t][1]==n);
    ch[t][isr]=ch[n][!isr],pre[ch[n][!isr]]=t;
    pre[n]=pre[t],ch[pre[t]][ch[pre[t]][1]==t]=n;
    pre[t]=n,ch[n][!isr]=t;
    flow(t);
}
inline void splay(int n,int goal)
{
    int f,ff;
    while(pre[n]!=goal)
    {
        f=pre[n],ff=pre[f];
 
        if(goal==ff)
            rotate(n);
        else if((ch[ff][1]==f)==(ch[f][1]==n))
            rotate(f),rotate(n);
        else
            rotate(n),rotate(n);
    }
    flow(n);
    if(!goal)
        root=n;
}
 
void Top(int t){
    splay(t,0);
    int x=ch[t][1];
    while(ch[x][0])
        x=ch[x][0];
    splay(x,t);
    ch[x][0]=ch[t][0],pre[ch[t][0]]=x;
    ch[t][0]=0;
    //因为算法的特殊性.root不能变为t;
    flow(t);
}
 
int Rank(int n){
    int t=root;
    while(1){
        if(num[ch[t][0]]<n&&num[ch[t][0]]+end[t]-beg[t]+1>=n)
            break;
        if(n<=num[ch[t][0]])
            t=ch[t][0];
        else {
            n-=num[ch[t][0]]+end[t]-beg[t]+1,t=ch[t][1];
        }
    }
    int ans=beg[t]+n-1-num[ch[t][0]];
    splay(t,0);
    return ans;
}
int Query(int x){
    splay(x,0);
    return num[ch[x][0]]+1;
}
 
int Bisearch(int n)
{
    int l=1,r=N,mid;
 
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(beg[mid]>n)
            r=mid-1;
        else if(end[mid]<n)
            l=mid+1;
        else
            return mid;
    }
    return l;
}
int main(){
    int t,tt=0,val,i,j;
    char str[10];
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&q);
        k=0;
        na=0;
        for(i=0;i<q;i++){
            scanf("%s %d",str,&val);
            re[k]=str[0],req[k++]=val;
            if(str[0]=='T'){
                a[na++]=val;
            }
        }
        sort(a,a+na);
        for(j=i=1;i<na;i++)
            if(a[i]!=a[i-1])
                a[j++]=a[i];
        na=j;j=1;
        if(a[0]>1){
            beg[j]=1,end[j++]=a[0]-1;
        }
        for(i=0;i<na;i++){
            end[j]=beg[j]=a[i],j++;
            if(i<na-1){
                if(a[i]+1<a[i+1]){
                    beg[j]=a[i]+1,end[j]=a[i+1]-1;
                    j++;
                }
            }else{
               beg[j]=a[i]+1,end[j]=n,j++;
            }
        }
        beg[j]=end[j]=n+1;j++;
        memset(ch,0,sizeof(int)*(j+2)*2);
        num[0]=0,N=j-1;
        for(i=1;i<=N;i++){
            num[i]=num[i-1]+end[i]-beg[i]+1;
            pre[i-1]=i,ch[i][0]=i-1;
        }pre[N]=0;
        root=N;
        printf("Case %d:\n",++tt);
        for(i=0;i<k;i++){
            if(re[i]=='T'){
                Top(Bisearch(req[i]));
            }else if(re[i]=='R'){
                printf("%d\n",Rank(req[i]));
            }else{
                j=Bisearch(req[i]);
                printf("%d\n",Query(j)+req[i]-beg[j]);
            }
        }
    }
    return 0;
}
/*
 * 这个的Splay树可以当作很好的模版。擦。我平时手敲时累死
 * HDU4441 
 * 源于 http://blog.csdn.net/acm_cxlove/article/details/8122288
 */
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 200005
#define N 200005
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
struct Splay_tree{
    LL sum[N];
    int size[N],pre[N],val[N],tot;
    int ch[N][2],tot1,root,s[N],tot2,cnt[N][2];    //cnt[0]表示的是正数个数,cnt[1]表示的是负数个数
    //debug部分copy from hh
    void Treaval(int x) {
        if(x) {
            Treaval(ch[x][0]);
            printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2c \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x]);
            Treaval(ch[x][1]);
        }
    }
    void debug() {printf("%d\n",root);Treaval(root);}
    //以上Debug
    inline void NewNode(int &r,int k,int father){
        r=++tot1;
        ch[r][0]=ch[r][1]=0;
        cnt[r][0]=k>0;
        cnt[r][1]=k<0;
        sum[r]=k;
        pre[r]=father;
        size[r]=1;
        val[r]=k;
    }
    inline void Push_Up(int x){
        if(x==0) return ;
        int l=ch[x][0],r=ch[x][1];
        size[x]=size[l]+size[r]+1;
        cnt[x][0]=cnt[l][0]+cnt[r][0]+(val[x]>0);
        cnt[x][1]=cnt[l][1]+cnt[r][1]+(val[x]<0);
        sum[x]=(LL)sum[l]+sum[r]+val[x];
    }
    inline void Init(){
        tot1=tot2=root=tot=0;
        ch[root][0]=ch[root][1]=pre[root]=size[root]=sum[0]=cnt[0][0]=cnt[0][1]=0;
        val[root]=0;
        NewNode(root,0,0);
        NewNode(ch[root][1],0,root);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    inline void Rotate(int x,int kind){
        int y=pre[x];
        ch[y][!kind]=ch[x][kind];
        pre[ch[x][kind]]=y;
        if(pre[y])
            ch[pre[y]][ch[pre[y]][1]==y]=x;
        pre[x]=pre[y];
        ch[x][kind]=y;
        pre[y]=x;
        Push_Up(y);
    }
    inline void Splay(int r,int goal){
        while(pre[r]!=goal){
            if(pre[pre[r]]==goal)
                Rotate(r,ch[pre[r]][0]==r);
            else{
                int y=pre[r];
                int kind=(ch[pre[y]][0]==y);
                if(ch[y][kind]==r){
                    Rotate(r,!kind);
                    Rotate(r,kind);
                }
                else{
                    Rotate(y,kind);
                    Rotate(r,kind);
                }
            }
        }
        Push_Up(r);
        if(goal==0) root=r;
    }
    inline void RotateTo(int k, int goal) {
        int x=root;
        while(k!=size[ch[x][0]]+1){
            if (k<=size[ch[x][0]]){
                x=ch[x][0];
            }else{
                k-=(size[ch[x][0]]+1);
                x=ch[x][1];
            }
        }
        Splay(x,goal);
    }
    inline int Get_Kth(int r,int k){
        int t=size[ch[r][0]]+1;
        if(t==k) return r;
        if(t>k) return Get_Kth(ch[r][0],k);
        else return Get_Kth(ch[r][1],k-t);
    }
    inline int Insert(int pos,int k){
        tot++;
        RotateTo(pos,0);
        RotateTo(pos+1,root);
        NewNode(Key_value,k,ch[root][1]);
        Push_Up(ch[root][1]);
        Push_Up(root);
        return Key_value;
    }
    inline void Delete(int r){
        tot--;
        Splay(r,0);
        int pos=size[ch[r][0]];
        RotateTo(pos,0);
        RotateTo(pos+2,root);
        s[tot2++]=Key_value;
        Key_value=0;
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    //找第n+1个负数的位置
    inline int find(int x,int n){
        int l=ch[x][0],r=ch[x][1];
        if(cnt[l][1]==n&&val[x]<0) {Splay(x,0);return size[ch[root][0]];}
        else if(cnt[l][1]>=n+1) return find(l,n);
        else return find(r,n-cnt[l][1]-(val[x]<0));
    }
    inline void InOrder(int r){
        if(r==0)
            return;
        InOrder(ch[r][0]);
        printf("%d ",val[r]);
        InOrder(ch[r][1]);
    }
    inline void Print(){
        RotateTo(1,0);
        RotateTo(tot+2,root);
        InOrder(Key_value);
        printf("\n");
    }
}splay;
struct Segment_tree{
    int left,right,mmin;
}L[N*4];
int position[N][2];
void Push_Up(int step){
    L[step].mmin=min(L[lson].mmin,L[rson].mmin);
}
void Bulid(int step,int l,int r){
    L[step].left=l;
    L[step].right=r;
    if(l==r){
        L[step].mmin=l;
        return;
    }
    int m=(l+r)/2;
    Bulid(lson,l,m);
    Bulid(rson,m+1,r);
    Push_Up(step);
}
//flag为1表示是插入,flag为0表示是删除
void Update(int step,int pos,int flag){
    if(L[step].left==pos&&pos==L[step].right){
        if(flag) L[step].mmin=inf;
        else L[step].mmin=L[step].left;
        return ;
    }
    int m=(L[step].left+L[step].right)/2;
    if(pos<=m) Update(lson,pos,flag);
    else Update(rson,pos,flag);
    Push_Up(step);
}
void Insert(int pos){
    int num=L[1].mmin;
    position[num][0]=splay.Insert(pos+1,num);
    splay.Splay(position[num][0],0);
    int n=splay.cnt[splay.ch[splay.root][0]][0];  //表示在+i之前有多少个正数
    //将-i插入到第n+1个负数左边
    if(splay.cnt[splay.root][1]<=n){
        int m=splay.size[splay.root]-2+1;
        position[num][1]=splay.Insert(m,-num);
        Update(1,num,1);  //插入线段树
    }
    else{
        int m=splay.find(splay.root,n);   //表示第n+1个负数是第m个数
        position[num][1]=splay.Insert(m,-num);
        Update(1,num,1);  //插入线段树
    }
}
void Remove(int k){
    splay.Delete(position[k][0]);
    splay.Delete(position[k][1]);
    Update(1,k,0);   //从线段树中移除
}
LL Query(int k){
    splay.Splay(position[k][0],0);
    splay.Splay(position[k][1],splay.root);
    return splay.sum[splay.ch[splay.ch[splay.root][1]][0]];
}
int main(){
    int cas=0,q;
    while(scanf("%d",&q)!=EOF){
        printf("Case #%d:\n",++cas);
        splay.Init();
        Bulid(1,1,q);
        while(q--){
            char str[10];int k;
            scanf("%s%d",str,&k);
            if(str[0]=='i') Insert(k);
            else if(str[0]=='r') Remove(k);
            else printf("%I64d\n",Query(k));
           // splay.Print();
        }
    }
    return 0;
}
//
//  1861.cpp
//  ACM_BZOJ
//
//  Created by ipqhjjybj on 13-9-9.
//  Copyright (c) 2013年 ipqhjjybj. All rights reserved.
//  第一道完全手敲得啊。任重道远。。
//
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cstring>
using namespace std;
#define Key_Tree child[child[root][1]][0]
 
int n;
struct SplayTree{
    const static int maxn=111111;
    int n,tot,root;
    int pre[maxn],size[maxn];//flex[maxn]
    int child[maxn][2];
    int a[maxn];
 
    void Travel(int u){
        if(!u) return;
        printf("u=%d c0=%d c1=%d s0=%d s1=%d\n",u,child[u][0],child[u][1],size[child[u][0]]+size[child[u][1]]);
        Travel(child[u][0]);
        Travel(child[u][1]);
    }
    void Push_up(int &x){
        size[x]=size[child[x][0]]+size[child[x][1]]+1;
    }
 
    void Del_root(){
        int t=root;
        //printf("root=%d\n",root);
        //printf("child[%d][1]=%d\n",root,child[root][1]);
        if(child[root][1]){
            root=child[root][1];
           // printf("root=%d\n",root);
            Select(1,0);
            child[root][0]=child[t][0];
            if(child[t][0])
                pre[child[t][0]]=root;
        }else
            root=child[root][0];
        pre[root]=0;
        Push_up(root);
        child[t][0]=child[t][1]=0;//清空t
        size[t]=1;
    }
    //c==0 左旋  c==1 右旋
    inline void Rotate(int x,int c){
        int y=pre[x];
        //Pushdown(y),Pushdown(x);
        child[y][!c]=child[x][c];
        if(child[x][c]) pre[child[x][c]]=y;
        pre[x]=pre[y];
        if(pre[y]) child[pre[y]][child[pre[y]][1]==y]=x;
        child[x][c]=y;
        pre[y]=x;
        Push_up(y);
    }
    void Splay(int x,int f){
        //Push_down(x);
        while(pre[x]!=f){
            int y=pre[x],z=pre[y];
            //Push_down(z),Push_down(y),Push_down(x);
            if(pre[pre[x]]==f){
                Rotate(x,child[pre[x]][0]==x);
            }else{
                if(child[z][0]==y){
                    if(child[y][0]==x)
                        Rotate(y,1),Rotate(x,1);
                    else Rotate(x,0),Rotate(x,1);
                }else{
                    if(child[y][0]==x)
                        Rotate(x,1),Rotate(x,0);
                    else Rotate(y,0),Rotate(x,0);
                }
            }
        }
        Push_up(x);
        if(!f) root=x;
    }
    int Select(int k,int f){
        int x=root;
        while(1){
 
            if(k==size[child[x][0]]+1)
                break;
            if(k<=size[child[x][0]])
                x=child[x][0];
            else{
                k-=size[child[x][0]]+1;
                x=child[x][1];
            }
        }
        Splay(x,f);
        return x;
    }
    //after one number's
    void Insert(int t,int after){
        Select(after,0);
        int x=Select(after+1,root);
        Key_Tree=t;//或者child[x][0]=t;
        pre[t]=x;
        Push_up(t);
        Push_up(x);
    }
    void Top(int t){
        Select(1,0);
        child[root][0]=t;
        pre[t]=root;
        Push_up(t);
        Push_up(root);
    }
    int Find_kth(int k){
        int t=root;
        while(1){
            if(size[child[t][0]]+1==k)
                break;
            else if(size[child[t][0]]>=k)
                t=child[t][0];
            else
                k-=size[child[t][0]]+1,t=child[t][1];
        }
        return t;
    }
    void Init(int _n){
        n=_n;
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        memset(child,0,(n+3)*2*sizeof(int));
        for(int i=1;i<=n;i++){
            pre[i-1]=i;
            child[i][0]=i-1;
            size[i]=i;
        }pre[n]=n+1,child[n+1][0]=n,a[n+1]=n+1,pre[n+1]=0,root=n+1,a[0]=0;
        size[0]=0,size[n+1]=n+1;
        child[0][0]=child[0][1]=0;
        Map.clear();
        for(int i=1;i<=n;i++)
            Map[a[i]]=i;
    }
    map<int,int> Map;
}spt;
void Init(int n){
    spt.Init(n);
}
int Ask(int t){
    spt.Splay(t,0);
    return spt.size[spt.child[t][0]];
}
void Top(int t){
    spt.Splay(t,0);
    spt.Del_root();
    spt.Top(t);
}
int Query(int k){
    return spt.a[spt.Find_kth(k)];
}
void Bottom(int t){
    spt.Splay(t,0);
    spt.Del_root();
    spt.Insert(t,n-1);
}
void Insert(int t,int val){
    spt.Splay(t,0);
    int sz=spt.size[spt.child[t][0]];
    sz+=val;
    if(sz==0){  //个人的函数问题,需要特判
        Top(t);
        return;
    }else if(sz==n-1){
        Bottom(t);
        return;
    }
    spt.Del_root();
    spt.Insert(t,sz);
}
void Solve(int m){
    char str[10];
    int val,num;
    while(m--){
        scanf("%s",str);
 
        if(str[0]=='Q'){//query
            scanf("%d",&val);
            printf("%d\n",Query(val));
        }else if(str[0]=='T'){//top
            scanf("%d",&val);
            Top(spt.Map[val]);
        }else if(str[0]=='A'){//ask
            scanf("%d",&val);
            printf("%d\n",Ask(spt.Map[val]));
        }else if(str[0]=='B'){//bottom
            scanf("%d",&val);
            Bottom(spt.Map[val]);
        }else if(str[0]=='I'){//insert
            scanf("%d %d",&val,&num);
            if(num!=0)
                Insert(spt.Map[val],num);
        }
    }
}
int main(){
    int m;
 
    scanf("%d %d",&n,&m);
        Init(n);
        Solve(m);
 
    return 0;
}
个人工具
名字空间

变换
操作
导航
工具箱