紫薯例题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1e6+10,inf=0x3f3f3f3f;
 5 int rt[N],siz[N*40],ch[N*40][2],tot,n,d,ver;
 6 char buf[N],val[N*40];
 7 #define l(u) ch[u][0]
 8 #define r(u) ch[u][1]
 9 int rnd() {
10     const int M=(1ll<<31)-1,X=19260817;
11     static int seed=time(0)%M;
12     return seed=(ll)seed*X%M;
13 }
14 int newnode(char c) {int u=++tot; siz[u]=1,l(u)=r(u)=0,val[u]=c; return u;}
15 int cpy(int v) {int u=++tot; siz[u]=siz[v],l(u)=l(v),r(u)=r(v),val[u]=val[v]; return u;}
16 void pu(int u) {siz[u]=siz[l(u)]+siz[r(u)]+1;}
17 void sp(int w,int k,int& u,int& v) {
18     if(!w) {u=v=0; return;}
19     if(k<=siz[l(w)])v=cpy(w),sp(l(w),k,u,l(v)),pu(v);
20     else u=cpy(w),sp(r(w),k-(siz[l(w)]+1),r(u),v),pu(u);
21 }
22 void mg(int& w,int u,int v) {
23     if(!u||!v) {w=u|v; return;}
24     if(rnd()%(siz[u]+siz[v])<siz[u])w=u,mg(r(w),r(u),v);
25     else w=v,mg(l(w),u,l(v));
26     pu(w);
27 }
28 void build(int& u,int l,int r) {
29     if(l>r) {u=0; return;}
30     int mid=(l+r)>>1;
31     u=newnode(buf[mid]);
32     build(l(u),l,mid-1),build(r(u),mid+1,r),pu(u);
33 }
34 void ins(int& rt,int p) {
35     int n=strlen(buf);
36     int L,M,R;
37     build(M,0,n-1);
38     sp(rt,p,L,R),mg(L,L,M),mg(rt,L,R);
39 }
40 void del(int& rt,int p,int c) {
41     int L,M,R;
42     sp(rt,p+c-1,L,R),sp(L,p-1,L,M),mg(rt,L,R);
43 }
44 void dfs(int u) {
45     if(!u)return;
46     dfs(l(u)),putchar(val[u]),dfs(r(u));
47     if(val[u]=='c')++d;
48 }
49 void pr(int& rt,int p,int c) {
50     int L,M,R;
51     sp(rt,p+c-1,L,R),sp(L,p-1,L,M);
52     dfs(M),puts("");
53     mg(L,L,M),mg(rt,L,R);
54 }
55 int main() {
56     scanf("%d",&n);
57     for(int i=1; i<=n; ++i) {
58         int f;
59         scanf("%d",&f);
60         if(f==1) {
61             int p;
62             scanf("%d%s",&p,buf),p-=d;
63             ++ver,ins(rt[ver]=rt[ver-1],p);
64         } else if(f==2) {
65             int p,c;
66             scanf("%d%d",&p,&c),p-=d,c-=d;
67             ++ver,del(rt[ver]=rt[ver-1],p,c);
68         } else {
69             int v,p,c;
70             scanf("%d%d%d",&v,&p,&c),v-=d,p-=d,c-=d;
71             pr(rt[v],p,c);
72         }
73     }
74     return 0;
75 }