比较基本的操作。
#include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 99999999 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define key_value ch[ch[root][1]][0] using namespace std; const int MAXN = 2200010; int pre[MAXN],rev[MAXN],siz[MAXN],ch[MAXN][2],s[MAXN],tot1,tot2,root; int n; char a[MAXN],key[MAXN]; void Treavel(int x) { if(x) { Treavel(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d key=%2c rev=%2d pre=%2d ",x,ch[x][0],ch[x][1],pre[x],siz[x],key[x],rev[x],pre[x]); Treavel(ch[x][1]); } } void debug() { printf("root:%d ",root); Treavel(root); } void Newnode(int &rt,int pa,int k) { if(tot2){ rt = s[tot2--]; } else { rt = ++tot1; } pre[rt] = pa; siz[rt] = 1; key[rt] = k; rev[rt] = 0; ch[rt][0] = ch[rt][1] = 0; } void pushup(int rt) { siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1; } void updata_rev(int rt) { if(!rt) return; rev[rt] ^= 1; swap(ch[rt][0],ch[rt][1]); } void pushdown(int rt) { if(rev[rt]){ updata_rev(ch[rt][0]); updata_rev(ch[rt][1]); rev[rt] = 0; } } void build(int &rt,int l,int r,int pa) { if(l > r) return ; int m = (l+r)/2; Newnode(rt,pa,a[m]); build(ch[rt][0],l,m-1,rt); build(ch[rt][1],m+1,r,rt); pushup(rt); } void Init() { root = tot1 = tot2 = 0; key[root] = pre[root] = rev[root] = siz[root] = 0; ch[root][0] = ch[root][1] = 0; Newnode(root,0,0); Newnode(ch[root][1],root,0); pushup(ch[root][1]); pushup(root); } void Rotate(int rt,int kind) { int y = pre[rt]; pushdown(y); pushdown(rt); ch[y][!kind] = ch[rt][kind]; pre[ch[rt][kind]] = y; if(pre[y]){ ch[pre[y]][ch[pre[y]][1]==y] = rt; } pre[rt] = pre[y]; ch[rt][kind] = y; pre[y] = rt; pushup(y); } void splay(int rt,int goal) { pushdown(rt); while(pre[rt] != goal) { if(pre[pre[rt]] == goal){ pushdown(pre[rt]); pushdown(rt); Rotate(rt,ch[pre[rt]][0]==rt); } else { pushdown(pre[pre[rt]]); pushdown(pre[rt]); pushdown(rt); int y = pre[rt]; int kind = ch[pre[y]][0]==y; if(ch[y][kind] == rt){ Rotate(rt,!kind); Rotate(rt,kind); } else { Rotate(y,kind); Rotate(rt,kind); } } } if(goal == 0) root = rt; pushup(rt); } int Get_kth(int rt,int k) { pushdown(rt); int t = siz[ch[rt][0]] + 1; if(t == k){ return rt; } else if(t > k){ return Get_kth(ch[rt][0],k); } else { return Get_kth(ch[rt][1],k-t); } } int Get_next(int rt) { pushdown(rt); int tmp = ch[rt][1]; while(ch[tmp][0]){ tmp = ch[tmp][0]; pushdown(tmp); } return tmp; } int Get_pre(int rt) { pushdown(rt); int tmp = ch[rt][0]; while(ch[tmp][1]){ tmp = ch[tmp][1]; pushdown(tmp); } return tmp; } void erase(int rt) { if(!rt) return; s[++tot2] = rt; erase(ch[rt][0]); erase(ch[rt][1]); } int main() { int i,j; while(~scanf("%d",&n)) { Init(); char c[20]; //debug(); while(n--) { scanf("%s",c); if(c[0] == 'I'){ int len; scanf("%d",&len); getchar(); gets(a); splay(Get_next(root),root); build(key_value,0,len-1,ch[root][1]); pushup(ch[root][1]); pushup(root); //debug(); } else if(c[0] == 'D'){ int x; scanf("%d",&x); int ret = siz[ch[root][0]] + 1; splay(Get_kth(root,ret+x+1),root); erase(key_value); pre[key_value] = 0; key_value = 0; pushup(ch[root][1]); pushup(root); //debug(); } else if(c[0] == 'R'){ int x; scanf("%d",&x); int ret = siz[ch[root][0]] + 1; splay(Get_kth(root,ret+x+1),root); updata_rev(key_value); pushup(ch[root][1]); pushup(root); //debug(); } else if(c[0] == 'G'){ printf("%c ",key[Get_next(root)]); } else if(c[0] == 'M'){ int x; scanf("%d",&x); splay(Get_kth(root,x+1),0); //debug(); } else if(c[0] == 'P'){ splay(Get_pre(root),0); //debug(); } else { splay(Get_next(root),0); //debug(); } } } }