题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1269
splay的裸题，和维修数列很像
数组一定要开够
不然连怎么死的都不知道，又WA又RE
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
#include<bits/stdc++.h> #define MAXN 2000010 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } struct SplayTree{ int son[MAXN][2],fa[MAXN],key[MAXN],val[MAXN],sz[MAXN]; int a[MAXN],nums[MAXN]; queue<int>q; bool rev[MAXN],lazy[MAXN]; int root,tot; bool getlr(int x){ return son[fa[x]][1]==x; } void uprev(int x){ if(!x)return; swap(son[x][0],son[x][1]); rev[x]^=1; } void pushup(int x){ int l=son[x][0],r=son[x][1]; sz[x]=sz[l]+sz[r]+1; } void pushdown(int x){ int l=son[x][0],r=son[x][1]; if(rev[x]){ uprev(l); uprev(r); rev[x]^=1; } } void Rotate(int x){ int f=fa[x],ff=fa[f],which=getlr(x); son[f][which]=son[x][which^1]; fa[son[f][which]]=f;fa[f]=x; son[x][which^1]=f;fa[x]=ff; if(ff)son[ff][son[ff][1]==f]=x; pushup(f); pushup(x); } void splay(int x,int to){ pushdown(x); for(int f=fa[x]; f!=to; f=fa[x]){ if(fa[f]!=to)Rotate(getlr(x)==getlr(f)?f:x); Rotate(x); } if(to==0)root=x; } int build(int l,int r){ if(l>r)return 0; int mid=(l+r)/2,tmp=nums[mid]; val[tmp]=a[mid]; fa[son[tmp][0]=build(l,mid-1)]=tmp; fa[son[tmp][1]=build(mid+1,r)]=tmp; sz[tmp]=sz[son[tmp][0]]+sz[son[tmp][1]]+1; fa[0]=0; if(l==r){ sz[tmp]=1; rev[tmp]=0; } pushup(tmp); return tmp; } void recycle(int x){ if(x==0)return; fa[x]=val[x]=sz[x]=rev[x]=0; q.push(x); recycle(son[x][0]);recycle(son[x][1]); son[x][0]=son[x][1]=0; } int split(int pos,int len){ int y=getkth(pos),x=getkth(pos+1+len); splay(y,0);splay(x,root); return son[x][0]; } void ins(int pos,int nn){ for(int i=1; i<=nn; i++){ char ch=getchar(); if(ch=='\n' || ch=='\r'){ i--; continue; } a[i]=(int)ch; } for(int i=1; i<=nn; i++){ if(!q.empty())nums[i]=q.front(),q.pop(); else nums[i]=++tot; } int now=build(1,nn); split(pos,0); fa[now]=son[root][1]; son[son[root][1]][0]=now; pushup(son[root][1]); pushup(root); } int getkth(int x){ int now=root; while(now){ pushdown(now); if(sz[son[now][0]]==x-1)return now; else if(sz[son[now][0]]<x)x-=sz[son[now][0]]+1,now=son[now][1]; else now=son[now][0]; } } void del(int pos,int len){ int tmp=split(pos,len),f=fa[tmp],ff=fa[f]; recycle(tmp);son[f][0]=0; pushup(f);pushup(ff); } void Rev(int pos,int len){ int tmp=split(pos,len),f=fa[tmp],ff=fa[f]; if(!lazy[tmp]){ uprev(tmp); pushup(f);pushup(ff); } } void print(int x){ if(!x)return; pushdown(x); print(son[x][0]); if(val[x])printf("%c",(char)val[x]); print(son[x][1]); } }tree; int main(){ int m=rd(); tree.a[1]=tree.a[2]=INT_MIN/3;tree.nums[1]=1;tree.nums[2]=2; tree.tot=2; tree.root=tree.build(1,2); char op[10]; int pos=0,len,k; while(m--){ scanf("%s",op); if(op[0]=='M')pos=rd(); if(op[0]=='P')pos--; if(op[0]=='N')pos++; if(op[0]=='I')len=rd(),tree.ins(pos+1,len); if(op[0]=='D')len=rd(),tree.del(pos+1,len); if(op[0]=='R')len=rd(),tree.Rev(pos+1,len); if(op[0]=='G')printf("%c\n",(char)tree.val[tree.getkth(pos+2)]); } return 0; } |
但是splay写起来很难受，我们就可以拿出rope来用了
stl大法好！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<bits/stdc++.h> #include<ext/rope> using namespace std; using namespace __gnu_cxx; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n=rd(),len,pos=0,l; char op[10],ch[2000020],ch1[2000020],c; crope a,b,tmp; main(){ while(n--){ scanf("%s",op); if(op[0]=='M')pos=rd(); if(op[0]=='P')pos--; if(op[0]=='N')pos++; if(op[0]=='G')printf("%c\n",a[pos]); if(op[0]=='I'){ l=rd();len=a.length(); for(int i=0; i<l; i++){ c=getchar(); if(c=='\n'||c=='\r'){i--;continue;} ch[i]=c; ch1[l-i-1]=c; } ch[l]=ch1[l]='\0'; a.insert(pos,ch); b.insert(len-pos,ch1); } if(op[0]=='D'){ l=rd(); len=a.length(); a.erase(pos,l); b.erase(len-pos-l,l); } if(op[0]=='R'){ l=rd(); len=a.length(); tmp=a.substr(pos,l); a=a.substr(0,pos)+b.substr(len-pos-l,l)+a.substr(pos+l,len-pos-l); b=b.substr(0,len-pos-l)+tmp+b.substr(len-pos,pos); } } } |
