写完维修数列 这不是水题嘛233333
//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=5000050;int n,pos=1,ch[N][2],fa[N],size[N],root,xx,cnt;char op[15],ins[N],v[N];void push_up(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}void rotate(int p){ int q=fa[p],y=fa[q],f=(ch[q][1]==p); ch[q][f]=ch[p][!f],fa[ch[q][f]]=q; ch[p][!f]=q,fa[q]=p,fa[p]=y; if(y)ch[y][ch[y][1]==q]=p; push_up(q);}void splay(int x,int tp){ for(int y;y=fa[x];rotate(x)){ if(y==tp)break; if(fa[y]!=tp){ if((ch[y][0]==x)^(ch[fa[y]][0]==y))rotate(x); else rotate(y); } }push_up(x); if(!tp)root=x;}int find(int x,int sz){ if(size[ch[x][0]]+1==sz)return x; else if(size[ch[x][0]]>=sz)return find(ch[x][0],sz); else return find(ch[x][1],sz-size[ch[x][0]]-1);}int build(int l,int r,int father){ if(l>r)return 0; int pos=++cnt; if(l==r){ size[pos]=1; fa[pos]=father; v[pos]=ins[l]; return pos; } int mid=(l+r)>>1; ch[pos][0]=build(l,mid-1,pos); fa[pos]=father;v[pos]=ins[mid]; ch[pos][1]=build(mid+1,r,pos); push_up(pos); return pos;}void check(int x){ if(ch[x][0])check(ch[x][0]); PRintf("%c",v[x]); if(ch[x][1])check(ch[x][1]);}int main(){ scanf("%d",&n); root=1,size[1]=2,ch[1][0]=2,size[2]=1,fa[2]=1,cnt=2; for(int i=1;i<=n;i++){ scanf("%s",op); if(op[0]=='I'){ int fx=find(root,pos),fy=find(root,pos+1); splay(fx,0),splay(fy,fx); scanf("%d",&xx); for(int j=1;j<=xx;j++) while(scanf("%c",&ins[j]),ins[j]<32); ch[fy][0]=build(1,xx,fy); push_up(fy),push_up(fx);// check(root); } else if(op[0]=='M')scanf("%d",&pos),pos++; else if(op[0]=='P')pos--; else if(op[0]=='N')pos++; else if(op[0]=='D'){ scanf("%d",&xx); xx=min(size[root],xx+pos+1); int fx=find(root,pos),fy=find(root,xx); splay(fx,0),splay(fy,fx); ch[fy][0]=0,push_up(fy),push_up(fx); } else{ scanf("%d",&xx); int fx=find(root,pos),fy=find(root,min(pos+xx+1,size[root])); splay(fx,0),splay(fy,fx); check(ch[fy][0]),puts(""); } }}新闻热点
疑难解答
