数据结构小结

我真是个弱菜啊。。。停课都一个月了还那么弱。。。想找数据结构水题的自己在下面翻

warning:本弱菜的语文能力相当拙计，看不懂我的文字描述的请看代码

平衡树入门级练习题，有了题目中的性质之后就非常好做了。平衡树上求前驱后继，记录当前平衡树内全是人还是全是宠物，注意相等的情况（也有可能是我想多了）

View Code

  1 #include <cstdio>
  2 
  3 const int maxn=80010;
  4 const int mod=1000000;
  5 const int inf=0x3f3f3f3f;
  6 
  7 int n,flag=-1,ans=0;
  8 
  9 struct Node
 10 {
 11     int v,size;
 12     Node* s[2];
 13     Node()
 14     {
 15         v=size=0;
 16     }
 17 };
 18 
 19 struct sbt
 20 {
 21     Node t[maxn],null;
 22     Node *root;
 23     int ne;
 24 
 25     sbt()
 26     {
 27         ne=0;
 28         null.s[0]=null.s[1]=&null;
 29         root=&null;
 30     }
 31 
 32     inline void _rot(Node* &now,int l)
 33     {
 34         int r=!l;
 35         Node* s=now->s[l];
 36         now->s[l]=s->s[r];
 37         s->s[r]=now;
 38         s->size=now->size;
 39         now->size=now->s[0]->size+now->s[1]->size+1;
 40         now=s;
 41     }
 42 
 43     void _maintain(Node* &now,int l)
 44     {
 45         int r=!l;
 46         if (now->s[l]->s[l]->size > now->s[r]->size)
 47             _rot(now,l);
 48         else
 49         {
 50             if (now->s[l]->s[r]->size > now->s[r]->size)
 51             {
 52                 _rot(now->s[l],r);
 53                 _rot(now,l);
 54             }
 55             else
 56                 return;
 57         }
 58         _maintain(now->s[0],0);
 59         _maintain(now->s[1],1);
 60         _maintain(now,0);
 61         _maintain(now,1);
 62     }
 63 
 64     void insert(Node* &now,int v)
 65     {
 66         if (now == &null)
 67         {
 68             now=&t[ne++];
 69             now->v=v;
 70             now->size=1;
 71             now->s[0]=now->s[1]=&null;
 72             return;
 73         }
 74         now->size++;
 75         if (v < now->v)
 76             insert(now->s[0],v);
 77         else
 78             insert(now->s[1],v);
 79         _maintain(now,v >= now->v);
 80     }
 81 
 82     inline int pred(int v)
 83     {
 84         Node* now=root;
 85         int ans=-inf;
 86         while (1)
 87         {
 88             if (now == &null)
 89                 return ans;
 90             if (v <= now->v)
 91                 now=now->s[0];
 92             else
 93             {
 94                 ans=now->v;
 95                 now=now->s[1];
 96             }
 97         }
 98     }
 99 
100     inline int suc(int v)
101     {
102         Node* now=root;
103         int ans=inf;
104         while (1)
105         {
106             if (now == &null)
107                 return ans;
108             if (v >= now->v)
109                 now=now->s[1];
110             else
111             {
112                 ans=now->v;
113                 now=now->s[0];
114             }
115         }
116     }
117 
118     inline bool find(int v)
119     {
120         Node* now=root;
121         while (1)
122         {
123             if (now == &null)
124                 return 0;
125             if (now->v == v)
126                 return 1;
127             now=now->s[v >= now->v];
128         }
129     }
130 
131     int del(Node* &now,int v)
132     {
133         now->size--;
134         if (now->v == v || (v < now->v && now->s[0] == &null) || (v > now->v && now->s[1] == &null))
135         {
136             int t=now->v;
137             if (now->s[0] == &null)
138                 now=now->s[1];
139             else
140             {
141                 if (now->s[1] == &null)
142                     now=now->s[0];
143                 else
144                     now->v=del(now->s[1],0);
145             }
146             return t;
147         }
148         else
149         {
150             if (v < now->v)
151                 del(now->s[0],v);
152             else
153                 del(now->s[1],v);
154         }
155     }
156 }t;
157 
158 int main()
159 {
160     scanf("%d",&n);
161     int x,y;
162     for (int i=1;i<=n;i++)
163     {
164         scanf("%d%d",&x,&y);
165         if (flag == -1)
166         {
167             flag=x;
168             t.insert(t.root,y);
169         }
170         else
171         {
172             if (flag == x)
173                 t.insert(t.root,y);
174             else
175             {
176                 int l,r;
177                 if (t.find(y))
178                     t.del(t.root,y);
179                 else
180                 {
181                     l=t.pred(y);
182                     r=t.suc(y);
183                     if (y-l <= r-y)
184                     {
185                         ans+=y-l;
186                         ans%=mod;
187                         t.del(t.root,l);
188                     }
189                     else
190                     {
191                         ans+=r-y;
192                         ans%=mod;
193                         t.del(t.root,r);
194                     }
195                 }
196                 if (t.root->size == 0)
197                     flag=-1;
198             }
199         }
200     }
201     printf("%d\n",ans);
202     return 0;
203 }

bzoj1503

同样的水题，其实这道题用splay很好写的，但是我为了练习sbt。。。刚开始想的是在平衡树上直接修改值，然后加懒惰标记，但后来发现有更好的办法，记录全部的修改值，每次插入的时候先修改再插入，可以很好地降低常数

View Code

  1 #include <cstdio>
  2 
  3 const int maxn=100010;
  4 
  5 int n,min,add;
  6 
  7 struct Node
  8 {
  9     int size,v;
 10     Node *s[2];
 11     Node()
 12     {
 13         size=v=0;
 14     }
 15 };
 16 
 17 struct sbt
 18 {
 19     Node t[maxn],null;
 20     Node *root;
 21     int ne;
 22 
 23     sbt()
 24     {
 25         ne=0;
 26         null.s[0]=null.s[1]=&null;
 27         root=&null;
 28     }
 29 
 30     inline void _rot(Node* &now,int l)
 31     {
 32         int r=!l;
 33         Node *s=now->s[l];
 34         now->s[l]=s->s[r];
 35         s->s[r]=now;
 36         s->size=now->size;
 37         now->size=now->s[0]->size+now->s[1]->size+1;
 38         now=s;
 39     }
 40 
 41     void _maintain(Node* &now,int l)
 42     {
 43         int r=!l;
 44         if (now->s[l]->s[l]->size > now->s[r]->size)
 45             _rot(now,l);
 46         else
 47         {
 48             if (now->s[l]->s[r]->size > now->s[r]->size)
 49             {
 50                 _rot(now->s[l],r);
 51                 _rot(now,l);
 52             }
 53             else
 54                 return;
 55         }
 56         _maintain(now->s[0],0);
 57         _maintain(now->s[1],1);
 58         _maintain(now,0);
 59         _maintain(now,1);
 60     }
 61 
 62     void insert(Node* &now,int v)
 63     {
 64         if (now == &null)
 65         {
 66             now=&t[++ne];
 67             now->v=v;
 68             now->size=1;
 69             now->s[0]=now->s[1]=&null;
 70             return;
 71         }
 72         now->size++;
 73         if (v < now->v)
 74             insert(now->s[0],v);
 75         else
 76             insert(now->s[1],v);
 77         _maintain(now,v >= now->v);
 78     }
 79 
 80     void del(Node* &now)
 81     {
 82         if (now == &null)
 83             return;
 84         if (now->v+add < min)
 85         {
 86             now=now->s[1];
 87             del(now);
 88         }
 89         else
 90         {
 91             del(now->s[0]);
 92             now->size=now->s[0]->size+now->s[1]->size+1;
 93         }
 94     }
 95 
 96     inline int find(int v)
 97     {
 98         Node* now=root;
 99         while (1)
100         {
101             if (now == &null)
102                 return -1;
103             if (now->s[1]->size+1 == v)
104                 return now->v+add;
105             if (v <= now->s[1]->size)
106                 now=now->s[1];
107             else
108             {
109                 v-=now->s[1]->size+1;
110                 now=now->s[0];
111             }
112         }
113     }
114 
115     void travel(Node* now)
116     {
117         if (now->s[0] != &null)
118             travel(now->s[0]);
119         printf("%d\n",now->v+add);
120         if (now->s[1] != &null)
121             travel(now->s[1]);
122     }
123 }t;
124 
125 int main()
126 {
127     scanf("%d%d",&n,&min);
128     char s[2];
129     int x;
130     while (n--)
131     {
132         scanf("%s%d",s,&x);
133         if (s[0] == 'I')
134             if (x >= min)
135                 t.insert(t.root,x-add);
136         if (s[0] == 'A')
137             add+=x;
138         if (s[0] == 'S')
139         {
140             add-=x;
141             t.del(t.root);
142         }
143         if (s[0] == 'F')
144             printf("%d\n",t.find(x));
145     }
146     printf("%d\n",t.ne-t.root->size);
147     return 0;
148 }

bzoj1588

水题#3，平衡树上求前驱后继，比第一题还要基础

View Code

  1 #include <cstdio>
  2 
  3 const int maxn=100010;
  4 const int inf=0x3f3f3f3f;
  5 
  6 struct Node
  7 {
  8     Node* s[2];
  9     int size,v;
 10 };
 11 
 12 struct sbt
 13 {
 14     Node t[maxn],null;
 15     Node* root;
 16     int ne;
 17 
 18     sbt()
 19     {
 20         null.s[0]=null.s[1]=&null;
 21         null.v=null.size=0;
 22         ne=0;
 23         root=&null;
 24     }
 25 
 26     inline void _rot(Node* &now,int l)
 27     {
 28         int r=!l;
 29         Node* s=now->s[l];
 30         s->size=now->size;
 31         now->s[l]=s->s[r];
 32         s->s[r]=now;
 33         now->size=now->s[0]->size+now->s[1]->size+1;
 34         now=s;
 35     }
 36 
 37     void _maintain(Node* &now,int l)
 38     {
 39         int r=!l;
 40         if (now->s[l]->s[l]->size > now->s[r]->size)
 41             _rot(now,l);
 42         else
 43         {
 44             if (now->s[l]->s[r]->size > now->s[r]->size)
 45             {
 46                 _rot(now->s[l],r);
 47                 _rot(now,l);
 48             }
 49             else
 50                 return;
 51         }
 52         _maintain(now->s[0],0);
 53         _maintain(now->s[1],1);
 54         _maintain(now,0);
 55         _maintain(now,1);
 56     }
 57 
 58     void insert(Node* &now,int v)
 59     {
 60         if (now == &null)
 61         {
 62             now=&t[ne++];
 63             now->v=v;
 64             now->size=1;
 65             now->s[0]=now->s[1]=&null;
 66             return;
 67         }
 68         now->size++;
 69         if (v >= now->v)
 70             insert(now->s[1],v);
 71         else
 72             insert(now->s[0],v);
 73         _maintain(now,v >= now->v);
 74     }
 75 
 76     inline int pred(int v)
 77     {
 78         int ans=-inf;
 79         Node* now=root;
 80         while (1)
 81         {
 82             if (now == &null)
 83                 break;
 84             if (v < now->v)
 85                 now=now->s[0];
 86             else
 87             {
 88                 ans=now->v;
 89                 now=now->s[1];
 90             }
 91         }
 92         return ans;
 93     }
 94 
 95     inline int suc(int v)
 96     {
 97         int ans=inf;
 98         Node* now=root;
 99         while (1)
100         {
101             if (now == &null)
102                 break;
103             if (v > now->v)
104                 now=now->s[1];
105             else
106             {
107                 ans=now->v;
108                 now=now->s[0];
109             }
110         }
111         return ans;
112     }
113 }t;
114 
115 inline int min(int a,int b)
116 {
117     if (a < b)
118         return a;
119     return b;
120 }
121 
122 inline int abs(int x)
123 {
124     if (x >= 0)
125         return x;
126     return -x;
127 }
128 
129 int main()
130 {
131     int n,x;
132     int sum=0;
133     scanf("%d",&n);
134     scanf("%d",&x);
135     sum=x;
136     t.insert(t.root,x);
137     for (int i=2;i<=n;i++)
138     {
139         x=0;
140         scanf("%d",&x);
141         sum+=min(abs(x-t.pred(x)),abs(t.suc(x)-x));
142         t.insert(t.root,x);
143     }
144     printf("%d",sum);
145     return 0;
146 }

bzoj1269

喜闻乐见的splay练习题，splay维护字符串，注意rotate的时候打上标记，否则很有可能会T掉。一直以为只有splay才能区间反转，但后来听crf大神说有人用treap写过了，各种膜拜orz

View Code

  1 #include <cstdio>
  2 
  3 const int maxn=1024*1024*3;
  4 
  5 int n;
  6 char s[maxn],st[10];
  7 
  8 struct Node
  9 {
 10     int size;
 11     bool rot;
 12     char ch;
 13     Node *par,*s[2];
 14     Node()
 15     {
 16         size=0;
 17         rot=false;
 18     }
 19 };
 20 
 21 struct splay
 22 {
 23     Node t[maxn],null;
 24     Node* root;
 25     int size;
 26     splay()
 27     {
 28         root=&t[1];
 29         size=2;
 30         null.par=null.s[0]=null.s[1]=&null;
 31         t[1].s[0]=&null;t[1].s[1]=&t[2];t[1].par=&null;t[1].size=2;
 32         t[2].s[0]=&null;t[2].s[1]=&null;t[2].par=&t[1];t[2].size=1;
 33     }
 34 
 35     void _update(Node* now)
 36     {
 37         now->size=now->s[0]->size+now->s[1]->size+1;
 38     }
 39 
 40     void _pushdown(Node* now)
 41     {
 42         if (now != &null && now->rot)
 43         {
 44             now->s[0]->rot^=1;
 45             now->s[1]->rot^=1;
 46             Node* temp=now->s[0]->s[0];
 47             now->s[0]->s[0]=now->s[0]->s[1];
 48             now->s[0]->s[1]=temp;
 49             temp=now->s[1]->s[0];
 50             now->s[1]->s[0]=now->s[1]->s[1];
 51             now->s[1]->s[1]=temp;
 52             now->rot=false;
 53         }
 54     }
 55 
 56     void _rot(Node* now,int l)
 57     {
 58         int r=!l;
 59         Node* s=now->s[l];
 60         Node* p=now->par;
 61         (now->s[l]=s->s[r])->par=now;
 62         (s->s[r]=now)->par=s;
 63         s->par=p;
 64         if (p != &null)
 65             p->s[now == p->s[1]]=s;
 66         _update(now);
 67         _update(s);
 68     }
 69 
 70     void _splay(Node* now,Node* goal)
 71     {
 72         while (now->par != goal)
 73         {
 74             Node* p=now->par;
 75             Node* g=p->par;
 76             _pushdown(g);
 77             _pushdown(p);
 78             bool dp=now == p->s[1];
 79             bool dg=p == g->s[1];
 80             if (g == goal)
 81             {
 82                 _rot(p,dp);
 83             }
 84             else
 85             {
 86                 if (dp == dg)
 87                 {
 88                     _rot(g,dg);
 89                     _rot(p,dp);
 90                 }
 91                 else
 92                 {
 93                     _rot(p,dp);
 94                     _rot(g,dg);
 95                 }
 96             }
 97         }
 98         if (goal == &null)
 99             root=now;
100     }
101 
102     Node* _select(int v)
103     {
104         Node* now=root;
105         while (v)
106         {
107             _pushdown(now);
108             if (now->s[0]->size+1 == v)
109                 return now;
110             else
111             {
112                 if (v <= now->s[0]->size)
113                     now=now->s[0];
114                 else
115                 {
116                     v-=now->s[0]->size+1;
117                     now=now->s[1];
118                 }
119             }
120         }
121         return &null;
122     }
123 
124     void insert(int pos,int len)
125     {
126         Node* p=_select(pos);
127         Node* q=_select(pos+1);
128         _splay(p,&null);
129         _splay(q,root);
130         Node* now=root;
131         now->size+=len;
132         now=now->s[1];
133         now->size+=len;
134         Node* par=now;
135         for (int i=1;i<=len;i++)
136         {
137             scanf("%c",&s[i]);
138             if (s[i] == '\n' || s[i] == '\r')
139                 i--;
140         }
141         for (int i=1;i<=len;i++)
142         {
143             size++;
144             now=&t[size];
145             (par->s[0]=now)->par=par;
146             now->s[0]=now->s[1]=&null;
147             now->size=len-i+1;
148             now->ch=s[len-i+1];
149             par=now;
150         }
151         _splay(now,&null);
152     }
153 
154     void del(int pos,int len)
155     {
156         Node* p=_select(pos);
157         Node* q=_select(pos+len+1);
158         _splay(p,&null);
159         _splay(q,root);
160         root->s[1]->s[0]=&null;
161         _update(root->s[1]);
162         _update(root);
163     }
164 
165     void rot(int pos,int len)
166     {
167         Node* p=_select(pos);
168         Node* q=_select(pos+len+1);
169         _splay(p,&null);
170         _splay(q,root);
171         Node* now=root->s[1]->s[0];
172         now->rot^=1;
173         Node* temp=now->s[0];
174         now->s[0]=now->s[1];
175         now->s[1]=temp;
176     }
177 
178     void print(int pos)
179     {
180         Node* now=_select(pos);
181         _splay(now,&null);
182         printf("%c",now->ch);
183         printf("\n");
184     }
185 }t;
186 
187 int main()
188 {
189     int pos=1,len;
190     scanf("%d",&n);
191     while (n--)
192     {
193         scanf("%s",st);
194         if (st[0] == 'M')
195         {
196             scanf("%d",&pos);
197             pos++;
198         }
199         if (st[0] == 'I')
200         {
201             scanf("%d",&len);
202             char c='~';
203             while (c != '\n' && c != '\r')
204                 c=getchar();
205             t.insert(pos,len);
206         }
207         if (st[0] == 'D')
208         {
209             scanf("%d",&len);
210             t.del(pos,len);
211         }
212         if (st[0] == 'R')
213         {
214             scanf("%d",&len);
215             t.rot(pos,len);
216         }
217         if (st[0] == 'G')
218         {
219             t.print(pos+1);
220         }
221         if (st[0] == 'P')
222             pos--;
223         if (st[0] == 'N')
224             pos++;
225     }
226     return 0;
227 }

bzoj1901

伟大的主席发明了主席树，于是划分树基本成为了历史。。。带修改的区间第K大，树状数组套主席树，对主席树还不了解的同学可以去seter大神的博客看，虽然他的代码我完全看不懂。。。

View Code

  1 #include <cstdio>
  2 #include <algorithm>
  3 
  4 using namespace std;
  5 
  6 const int maxn=100010;
  7 const int maxm=3000010;
  8 
  9 struct Node
 10 {
 11     Node* s[2];
 12     int size;
 13     Node()
 14     {
 15         size=0;
 16     }
 17 }t[maxm],*root[maxn],*L[30],*R[30],null;
 18 
 19 int ne=0,size,n,m;
 20 int lsize,rsize;
 21 int a[maxn],b[maxn];
 22 int p[maxn],q[maxn],k[maxn];
 23 char ch[maxn][3];
 24 
 25 Node* build(int val,int l,int r)
 26 {
 27     Node* now=&t[ne++];
 28     now->s[0]=now->s[1]=&null;
 29     now->size=1;
 30     if (l == r)
 31         return now;
 32     int mid=(l+r)>>1;
 33     if (val <= mid)
 34         now->s[0]=build(val,l,mid);
 35     else
 36         now->s[1]=build(val,mid+1,r);
 37     return now;
 38 }
 39 
 40 void update(Node* now,int val,int l,int r,int flag)
 41 {
 42     while (1)
 43     {
 44         now->size+=flag;
 45         if (l == r)
 46             break;
 47         int mid=(l+r)>>1;
 48         if (val <= mid)
 49         {
 50             if (now->s[0] == &null)
 51             {
 52                 now->s[0]=build(val,l,mid);
 53                 return;
 54             }
 55             else
 56             {
 57                 now=now->s[0];
 58                 r=mid;
 59             }
 60         }
 61         else
 62         {
 63             if (now->s[1] == &null)
 64             {
 65                 now->s[1]=build(val,mid+1,r);
 66                 return;
 67             }
 68             else
 69             {
 70                 now=now->s[1];
 71                 l=mid+1;
 72             }
 73         }
 74     }
 75 }
 76 
 77 void bit_update(int now,int val,int flag)
 78 {
 79     for (;now <= n;now+=now & -now)
 80     {
 81         if (root[now] == &null)
 82             root[now]=build(val,1,size);
 83         else
 84             update(root[now],val,1,size,flag);
 85     }
 86 }
 87 
 88 int query(int l,int r,int k)
 89 {
 90     if (l == r)
 91         return l;
 92     int lsum=0,rsum=0,del,mid=(l+r)>>1;
 93     for (int i=1;i<=lsize;i++)
 94         lsum+=L[i]->s[0]->size;
 95     for (int i=1;i<=rsize;i++)
 96         rsum+=R[i]->s[0]->size;
 97     del=rsum-lsum;
 98     if (k <= del)
 99     {
100         for (int i=1;i <= lsize;i++)
101             L[i]=L[i]->s[0];
102         for (int i=1;i <= rsize;i++)
103             R[i]=R[i]->s[0];
104         return query(l,mid,k);
105     }
106     else
107     {
108         for (int i=1;i <= lsize;i++)
109             L[i]=L[i]->s[1];
110         for (int i=1;i <= rsize;i++)
111             R[i]=R[i]->s[1];
112         return query(mid+1,r,k-del);
113     }
114 }
115 
116 int ask(int l,int r,int k)
117 {
118     lsize=rsize=0;
119     if (!l)
120         L[++lsize]=&null;
121     else
122         for (;l > 0;l-=l & -l)
123             L[++lsize]=root[l];
124     for (;r > 0;r-=r & -r)
125         R[++rsize]=root[r];
126     return query(1,size,k);
127 }
128 
129 int main()
130 {
131     null.s[0]=null.s[1]=&null;
132     scanf("%d%d",&n,&m);
133     for (int i=1;i <= n;i++)
134     {
135         scanf("%d",&a[i]);
136         b[i]=a[i];
137     }
138     size=n;
139     for (int i=1;i <= m;i++)
140     {
141         scanf("%s%d%d",ch[i],&p[i],&q[i]);
142         if (ch[i][0] == 'Q')
143             scanf("%d",&k[i]);
144         else
145             b[++size]=q[i];
146     }
147     sort(b+1,b+size+1);
148     size=unique(b+1,b+size+1)-b-1;
149     for (int i=1;i <= n;i++)
150         a[i]=lower_bound(b+1,b+size+1,a[i])-b;
151     for (int i=1;i <= n;i++)
152         root[i]=&null;
153     for (int i=1;i <= n;i++)
154         bit_update(i,a[i],1);
155     for (int i=1;i <= m;i++)
156     {
157         if (ch[i][0] == 'Q')
158             printf("%d\n",b[ask(p[i]-1,q[i],k[i])]);
159         else
160         {
161             int pos=lower_bound(b+1,b+size+1,q[i])-b;
162             bit_update(p[i],a[p[i]],-1);
163             a[p[i]]=pos;
164             bit_update(p[i],a[p[i]],1);
165         }
166     }
167     return 0;
168 }

bzoj2120

带修改的求区间不同数的个数，主席树维护后继（这里的后继指的是同样的数下一次出现的位置），__ty大神给我讲这道题的时候很不屑地说“数颜色你没写过？”，于是我就花了将近一天时间把这道题写了。。。

主席树上的值表示当前这个位置的颜色下一次出现的位置，那么求[l,r]中不同数的个数就可以转化为求[l,r]内大于r的数的个数，离散化颜色后对每个颜色建一个set，维护该种颜色出现的位置，修改时直接对前驱后继进行修改（注意判断前驱后继是否存在）

View Code

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <set>
  5 
  6 using namespace std;
  7 
  8 #define maxn 20010
  9 #define inf 0x3f3f3f3f
 10 
 11 set <int> col[maxn];
 12 set <int>::iterator it;
 13 
 14 struct Node
 15 {
 16     int size;
 17     Node* s[2];
 18     Node()
 19     {
 20         size=0;
 21     }
 22 }t[maxn*250],*root[maxn],null,*L[100],*R[100];
 23 
 24 int lsize,rsize;
 25 int ne=0,n,m,size;
 26 int a[maxn],b[maxn];
 27 char ch[maxn][2];
 28 int q[maxn][2];
 29 int now[maxn],prev[maxn],next[maxn];
 30 
 31 inline void read(int& x)
 32 {
 33     char ch;
 34     while (ch=getchar(),ch > '9' || ch < '0');
 35     x=ch-'0';
 36     while (ch=getchar(),ch <= '9' && ch >= '0')
 37         x=(x<<3)+x+x+ch-'0';
 38 }
 39 
 40 inline void update(Node* now,int val,int add)
 41 {
 42     int l=1,r=n+1;
 43     while (1)
 44     {
 45         now->size+=add;
 46         if (l == r)
 47             return;
 48         int mid=(l+r)>>1;
 49         if (val <= mid)
 50         {
 51             if (now->s[0] == &null)
 52             {
 53                 now->s[0]=&t[ne++];
 54                 now->s[0]->s[0]=now->s[0]->s[1]=&null;
 55             }
 56             now=now->s[0];
 57             r=mid;
 58         }
 59         else
 60         {
 61             if (now->s[1] == &null)
 62             {
 63                 now->s[1]=&t[ne++];
 64                 now->s[1]->s[0]=now->s[1]->s[1]=&null;
 65             }
 66             now=now->s[1];
 67             l=mid+1;
 68         }
 69     }
 70 }
 71 
 72 inline void bit_update(int pos,int val,int add)
 73 {
 74     for (;pos<=n;pos+=pos & -pos)
 75         update(root[pos],val,add);
 76 }
 77 
 78 inline int query(int l,int r)
 79 {
 80     lsize=rsize=0;
 81     int x=l,y=r,ans=0,k=r;
 82     for (;x;x-=x & -x)
 83         L[++lsize]=root[x];
 84     for (;y;y-=y & -y)
 85         R[++rsize]=root[y];
 86     l=1,r=n+1;
 87     while (1)
 88     {
 89         if (l == r)
 90         {
 91             for (int i=1;i<=lsize;i++)
 92                 ans-=L[i]->size;
 93             for (int i=1;i<=rsize;i++)
 94                 ans+=R[i]->size;
 95             break;
 96         }
 97         int mid=(l+r)>>1;
 98         if (k >= mid)
 99         {
100             for (int i=1;i<=lsize;i++)
101                 L[i]=L[i]->s[1];
102             for (int i=1;i<=rsize;i++)
103                 R[i]=R[i]->s[1];
104             l=mid+1;
105         }
106         else
107         {
108             for (int i=1;i<=lsize;i++)
109                 ans-=L[i]->s[1]->size;
110             for (int i=1;i<=rsize;i++)
111                 ans+=R[i]->s[1]->size;
112             for (int i=1;i<=lsize;i++)
113                 L[i]=L[i]->s[0];
114             for (int i=1;i<=rsize;i++)
115                 R[i]=R[i]->s[0];
116             r=mid;
117         }
118     }
119     return ans;
120 }
121 
122 int main()
123 {
124 //    freopen("1.in","r",stdin);
125 //    freopen("1.out","w",stdout);
126     read(n);
127     read(m);
128     for (int i=1;i<=n;i++)
129     {
130         read(a[i]);
131         b[i]=a[i];
132     }
133     size=n;
134     for (int i=1;i<=m;i++)
135     {
136         scanf("%s",ch[i]);
137         read(q[i][0]);
138         read(q[i][1]);
139         if (ch[i][0] == 'R')
140             b[++size]=q[i][1];
141     }
142     sort(b+1,b+size+1);
143     size=unique(b+1,b+size+1)-b-1;
144     for (int i=1;i<=n;i++)
145         a[i]=lower_bound(b+1,b+size+1,a[i])-b;
146     for (int i=1;i<=n;i++)
147     {
148         next[i]=n+1;
149         if (!now[a[i]])
150             now[a[i]]=i;
151         else
152         {
153             next[now[a[i]]]=i;
154             prev[i]=now[a[i]];
155             now[a[i]]=i;
156         }
157         col[a[i]].insert(i);
158     }
159     null.s[0]=null.s[1]=&null;
160     root[0]=&null;
161     for (int i=1;i<=n;i++)
162     {
163         root[i]=&t[ne++];
164         root[i]->s[0]=root[i]->s[1]=&null;
165     }
166     for (int i=1;i<=n;i++)
167         bit_update(i,next[i],1);
168     for (int i=1;i<=m;i++)
169         if (ch[i][0] == 'Q')
170             printf("%d\n",query(q[i][0]-1,q[i][1]));
171         else
172         {
173             int pos=q[i][0],val=lower_bound(b+1,b+size+1,q[i][1])-b;
174             if (prev[pos])
175             {
176                 bit_update(prev[pos],pos,-1);
177                 next[prev[pos]]=next[pos];
178                 bit_update(prev[pos],next[pos],1);
179             }
180             if (next[pos] != n+1)
181                 prev[next[pos]]=prev[pos];
182             col[a[pos]].erase(pos);
183             a[pos]=val;
184             it=col[val].upper_bound(pos);
185             bit_update(pos,next[pos],-1);
186             if (*it > pos)
187             {
188                 next[pos]=*it;
189                 prev[*it]=pos;
190             }
191             else
192                 next[pos]=n+1;
193             bit_update(pos,next[pos],1);
194             if (it != col[val].begin())
195             {
196                 it--;
197                 bit_update(*it,next[*it],-1);
198                 next[*it]=pos;
199                 prev[pos]=*it;
200                 bit_update(*it,next[*it],1);
201             }
202             else
203                 prev[pos]=0;
204             col[val].insert(pos);
205         }
206     return 0;
207 }

bzoj1146

历年CTSC唯一一道我做的起的水题（其实也是我唯一看过的题）。。。带修改的树上路径第K大。当年的标准做法是树链剖分+树套树，但是现在有了主席树。。。具体做法是倍增（tarjan好像要爆栈，非递归不会写）求LCA，在DFS序上建立主席树，具体的还是看代码吧。。。

View Code

  1 #include <cstdio>
  2 #include <algorithm>
  3 
  4 using namespace std;
  5 
  6 #define maxn 80010
  7 
  8 struct Node
  9 {
 10     int size;
 11     Node *s[2];
 12     Node()
 13     {
 14         size=0;
 15     }
 16 }t[maxn*150],*root[maxn],*L[100],*R[100],null;
 17 
 18 struct edge
 19 {
 20     int to;
 21     edge *next;
 22 }e[maxn<<1],*head[maxn];
 23 
 24 int n,m,size,ne=0;
 25 int lsize,rsize;
 26 int a[maxn],b[maxn<<1];
 27 int q[maxn][3];
 28 int bit[30];
 29 int l[maxn],r[maxn];
 30 int d[maxn],f[maxn][20],maxd;
 31 int sta[maxn],top=0;
 32 bool flag[maxn];
 33 
 34 inline void read(int &x)
 35 {
 36     char ch;
 37     while (ch=getchar(),ch > '9' || ch < '0');
 38     x=ch-'0';
 39     while (ch=getchar(),ch <= '9' && ch >= '0')
 40         x=(x<<3)+x+x+ch-'0';
 41 }
 42 
 43 inline void add_edge(int from,int to)
 44 {
 45     e[ne].to=to;
 46     e[ne].next=head[from];
 47     head[from]=&e[ne++];
 48 }
 49 
 50 inline void dfs()
 51 {
 52     sta[++top]=1;
 53     l[1]=++ne;
 54     flag[1]=1;
 55     d[1]=0;
 56     while (top)
 57     {
 58         int x=sta[top];
 59         if (!flag[x])
 60         {
 61             l[x]=++ne;
 62             flag[x]=1;
 63         }
 64         bool check=0;
 65         for (edge *p=head[x];p;p=p->next)
 66             if (!flag[p->to])
 67             {
 68                 sta[++top]=p->to;
 69                 check=1;
 70                 f[p->to][0]=x;
 71                 d[p->to]=d[x]+1;
 72                 break;
 73             }
 74         if (check)
 75             continue;
 76         else
 77         {
 78             r[x]=ne;
 79             top--;
 80         }
 81     }
 82 }
 83 
 84 inline void lca_pre()
 85 {
 86     maxd=lower_bound(bit+1,bit+21,n)-bit;
 87     for (int i=1;i<=maxd;i++)
 88         for (int j=1;j<=n;j++)
 89             f[j][i]=f[f[j][i-1]][i-1];
 90 }
 91 
 92 inline int get_lca(int x,int y)
 93 {
 94     if (x == y)
 95         return x;
 96     if (d[x] < d[y])
 97         x^=y^=x^=y;
 98     for (int i=maxd;i>=0;i--)
 99         if (d[x]-d[y] >= bit[i])
100             x=f[x][i];
101     if (x == y)
102         return x;
103     for (int i=maxd;i>=0;i--)
104         if (f[x][i] != f[y][i])
105         {
106             x=f[x][i];
107             y=f[y][i];
108         }
109     return f[x][0];
110 }
111 
112 inline void update(Node* now,int val,int add)
113 {
114     int l=1,r=size;
115     while (1)
116     {
117         now->size+=add;
118         if (l == r)
119             return;
120         int mid=(l+r)>>1;
121         if (val <= mid)
122         {
123             if (now->s[0] == &null)
124             {
125                 now->s[0]=&t[ne++];
126                 now->s[0]->s[0]=now->s[0]->s[1]=&null;
127             }
128             now=now->s[0];
129             r=mid;
130         }
131         else
132         {
133             if (now->s[1] == &null)
134             {
135                 now->s[1]=&t[ne++];
136                 now->s[1]->s[0]=now->s[1]->s[1]=&null;
137             }
138             now=now->s[1];
139             l=mid+1;
140         }
141     }
142 }
143 
144 inline void bit_update(int pos,int val,int add)
145 {
146     for (;pos<=n;pos+=pos & -pos)
147         update(root[pos],val,add);
148 }
149 
150 inline int query(int k)
151 {
152     int l=1,r=size;
153     while (1)
154     {
155         if (l == r)
156             return l;
157         int mid=(l+r)>>1,del=0;
158         for (int i=1;i<=lsize;i++)
159             del-=L[i]->s[1]->size;
160         for (int i=1;i<=rsize;i++)
161             del+=R[i]->s[1]->size;
162         if (k <= del)
163         {
164             for (int i=1;i<=lsize;i++)
165                 L[i]=L[i]->s[1];
166             for (int i=1;i<=rsize;i++)
167                 R[i]=R[i]->s[1];
168             l=mid+1;
169         }
170         else
171         {
172             for (int i=1;i<=lsize;i++)
173                 L[i]=L[i]->s[0];
174             for (int i=1;i<=rsize;i++)
175                 R[i]=R[i]->s[0];
176             k-=del;
177             r=mid;
178         }
179     }
180 }
181 
182 inline int ask(int x,int y,int k)
183 {
184     int lca=get_lca(x,y);
185     int flca=f[lca][0];
186     x=l[x];
187     y=l[y];
188     lca=l[lca];
189     flca=l[flca];
190     lsize=rsize=0;
191     for (;x;x-=x & -x)
192         R[++rsize]=root[x];
193     for (;y;y-=y & -y)
194         R[++rsize]=root[y];
195     for (;lca;lca-=lca & -lca)
196         L[++lsize]=root[lca];
197     for (;flca;flca-=flca & -flca)
198         L[++lsize]=root[flca];
199     int ans=0;
200     for (int i=1;i<=lsize;i++)
201         ans-=L[i]->size;
202     for (int i=1;i<=rsize;i++)
203         ans+=R[i]->size;
204     if (ans < k)
205         return -1;
206     return query(k);
207 }
208 
209 int main()
210 {
211     bit[0]=1;
212     for (int i=1;i<=20;i++)
213         bit[i]=bit[i-1]+bit[i-1];
214     read(n);
215     read(m);
216     for (int i=1;i<=n;i++)
217     {
218         read(a[i]);
219         b[i]=a[i];
220     }
221     size=n;
222     for (int i=1;i<n;i++)
223     {
224         int x,y;
225         read(x);
226         read(y);
227         add_edge(x,y);
228         add_edge(y,x);
229     }
230     for (int i=1;i<=m;i++)
231     {
232         read(q[i][0]);
233         read(q[i][1]);
234         read(q[i][2]);
235         if (!q[i][0])
236             b[++size]=q[i][2];
237     }
238     sort(b+1,b+size+1);
239     size=unique(b+1,b+size+1)-b-1;
240     for (int i=1;i<=n;i++)
241         a[i]=lower_bound(b+1,b+size+1,a[i])-b;
242     ne=0;
243     dfs();
244     lca_pre();
245     ne=0;
246     null.s[0]=null.s[1]=&null;
247     root[0]=&null;
248     for (int i=1;i<=n;i++)
249     {
250         root[i]=&t[ne++];
251         root[i]->s[0]=root[i]->s[1]=&null;
252     }
253     for (int i=1;i<=n;i++)
254     {
255         bit_update(l[i],a[i],1);
256         bit_update(r[i]+1,a[i],-1);
257     }
258     for (int i=1;i<=m;i++)
259     {
260         if (!q[i][0])
261         {
262             bit_update(l[q[i][1]],a[q[i][1]],-1);
263             bit_update(r[q[i][1]]+1,a[q[i][1]],1);
264             a[q[i][1]]=lower_bound(b+1,b+size+1,q[i][2])-b;
265             bit_update(l[q[i][1]],a[q[i][1]],1);
266             bit_update(r[q[i][1]]+1,a[q[i][1]],-1);
267         }
268         else
269         {
270             int ans=ask(q[i][1],q[i][2],q[i][0]);
271             if (ans != -1)
272                 printf("%d\n",b[ans]);
273             else
274                 printf("invalid request!\n");
275         }
276     }
277     return 0;
278 }

tarjan果然比倍增快。。。不过快了1200ms是什么心态

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4  
  5 using namespace std;
  6  
  7 #define maxn 80010
  8  
  9 struct Node
 10 {
 11     int size;
 12     Node* s[2];
 13 }t[maxn*160],*root[maxn],null,*L[100],*R[100];
 14  
 15 struct edge
 16 {
 17     int to;
 18     edge *next;
 19 }e[maxn<<1],*head[maxn];
 20  
 21 struct query
 22 {
 23     int to,num;
 24     query *next;
 25 }que[maxn<<1],*begin[maxn];
 26  
 27 int n,m,size,ne=0,lsize,rsize;
 28 int a[maxn],b[maxn<<1],q[maxn][3],lca[maxn];
 29 int l[maxn],r[maxn];
 30 int anc[maxn],f[maxn],fa[maxn],rank[maxn];
 31 bool flag[maxn];
 32  
 33 inline void add_edge(int from,int to)
 34 {
 35     e[ne].to=to;
 36     e[ne].next=head[from];
 37     head[from]=&e[ne++];
 38 }
 39  
 40 inline void add_query(int from,int to,int num)
 41 {
 42     que[ne].to=to;
 43     que[ne].num=num;
 44     que[ne].next=begin[from];
 45     begin[from]=&que[ne++];
 46 }
 47  
 48 inline void read(int &x)
 49 {
 50     char ch;
 51     while (ch=getchar(),ch > 57 || ch < 48);
 52     x=ch-48;
 53     while (ch=getchar(),ch <= 57 && ch >= 48)
 54         x=(x<<3)+x+x+ch-48;
 55 }
 56  
 57 int find(int now)
 58 {
 59     if (f[now] == now)
 60         return now;
 61     return f[now]=find(f[now]);
 62 }
 63  
 64 inline void _union(int x,int y)
 65 {
 66     int a=find(x);
 67     int b=find(y);
 68     if (a == b)
 69         return;
 70     if (rank[a] <= rank[b])
 71     {
 72         f[a]=b;
 73         rank[b]+=rank[a];
 74     }
 75     else
 76     {
 77         f[b]=a;
 78         rank[a]+=rank[b];
 79     }
 80 }
 81  
 82 void dfs(int now)
 83 {
 84     f[now]=now;
 85     anc[now]=now;
 86     flag[now]=1;
 87     l[now]=++ne;
 88     for (edge *p=head[now];p;p=p->next)
 89         if (!flag[p->to])
 90         {
 91             dfs(p->to);
 92             fa[p->to]=now;
 93             _union(now,p->to);
 94             anc[find(now)]=now;
 95         }
 96     for (query *q=begin[now];q;q=q->next)
 97         if (flag[q->to])
 98             lca[q->num]=anc[find(q->to)];
 99     r[now]=ne;
100 }
101  
102 inline void update(Node* now,int val,int flag)
103 {
104     int l=1,r=size;
105     while (1)
106     {
107         now->size+=flag;
108         if (l == r)
109             return;
110         int mid=(l+r)>>1;
111         if (val <= mid)
112         {
113             if (now->s[0] == &null)
114             {
115                 now->s[0]=&t[ne++];
116                 now->s[0]->s[0]=now->s[0]->s[1]=&null;
117                 now->s[0]->size=0;
118             }
119             now=now->s[0];
120             r=mid;
121         }
122         else
123         {
124             if (now->s[1] == &null)
125             {
126                 now->s[1]=&t[ne++];
127                 now->s[1]->s[0]=now->s[1]->s[1]=&null;
128                 now->s[1]->size=0;
129             }
130             now=now->s[1];
131             l=mid+1;
132         }
133     }
134 }
135  
136 inline void bit_update(int now,int val,int flag)
137 {
138     for (;now<=n;now+=now&-now)
139         update(root[now],val,flag);
140 }
141  
142 inline int query(int x,int y,int lca,int flca,int k)
143 {
144     lsize=rsize=0;
145     x=l[x];
146     y=l[y];
147     lca=l[lca];
148     flca=l[flca];
149     int del=0;
150     for (;x>0;x-=x&-x)
151     {
152         R[++rsize]=root[x];
153         del+=R[rsize]->size;
154     }
155     for (;y>0;y-=y&-y)
156     {
157         R[++rsize]=root[y];
158         del+=R[rsize]->size;
159     }
160     for (;lca>0;lca-=lca&-lca)
161     {
162         L[++lsize]=root[lca];
163         del-=L[lsize]->size;
164     }
165     for (;flca>0;flca-=flca&-flca)
166     {
167         L[++lsize]=root[flca];
168         del-=L[lsize]->size;
169     }
170     if (del < k)
171         return -1;
172     int l=1,r=size;
173     while (1)
174     {
175         if (l == r)
176             return l;
177         int mid=(l+r)>>1;
178         del=0;
179         for (int i=1;i<=rsize;i++)
180             del+=R[i]->s[1]->size;
181         for (int i=1;i<=lsize;i++)
182             del-=L[i]->s[1]->size;
183         if (k <= del)
184         {
185             for (int i=1;i<=lsize;i++)
186                 L[i]=L[i]->s[1];
187             for (int i=1;i<=rsize;i++)
188                 R[i]=R[i]->s[1];
189             l=mid+1;
190         }
191         else
192         {
193             for (int i=1;i<=lsize;i++)
194                 L[i]=L[i]->s[0];
195             for (int i=1;i<=rsize;i++)
196                 R[i]=R[i]->s[0];
197             k-=del;
198             r=mid;
199         }
200     }
201 }
202  
203 int main()
204 {
205     read(n);
206     read(m);
207     for (int i=1;i<=n;i++)
208     {
209         read(a[i]);
210         b[i]=a[i];
211     }
212     size=n;
213     for (int i=1;i<n;i++)
214     {
215         int x,y;
216         read(x);
217         read(y);
218         add_edge(x,y);
219         add_edge(y,x);
220     }
221     ne=0;
222     for (int i=1;i<=m;i++)
223     {
224         read(q[i][0]);
225         read(q[i][1]);
226         read(q[i][2]);
227         if (!q[i][0])
228             b[++size]=q[i][2];
229         else
230         {
231             add_query(q[i][1],q[i][2],i);
232             add_query(q[i][2],q[i][1],i);
233         }
234     }
235     ne=0;
236     sort(b+1,b+size+1);
237     size=unique(b+1,b+size+1)-b-1;
238     for (int i=1;i<=n;i++)
239         a[i]=lower_bound(b+1,b+size+1,a[i])-b;
240     null.s[0]=null.s[1]=&null;
241     null.size=0;
242     dfs(1);
243     ne=0;
244     for (int i=0;i<=n;i++)
245     {
246         root[i]=&t[ne++];
247         root[i]->s[0]=root[i]->s[1]=&null;
248         root[i]->size=0;
249     }
250     for (int i=1;i<=n;i++)
251     {
252         bit_update(l[i],a[i],1);
253         bit_update(r[i]+1,a[i],-1);
254     }
255     for (int i=1;i<=m;i++)
256     {
257         if (!q[i][0])
258         {
259             bit_update(l[q[i][1]],a[q[i][1]],-1);
260             bit_update(r[q[i][1]]+1,a[q[i][1]],1);
261             a[q[i][1]]=lower_bound(b+1,b+size+1,q[i][2])-b;
262             bit_update(l[q[i][1]],a[q[i][1]],1);
263             bit_update(r[q[i][1]]+1,a[q[i][1]],-1);
264         }
265         else
266         {
267             int ans=query(q[i][1],q[i][2],lca[i],fa[lca[i]],q[i][0]);
268             if (ans != -1)
269                 printf("%d\n",b[ans]);
270             else
271                 printf("invalid request!\n");
272         }
273     }
274     return 0;
275 }

bzoj1014

splay维护hash值，可以算半道数据结构题吧

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 #define maxn 300010
  5 
  6 const unsigned int mod=27;
  7 
  8 unsigned int hash[maxn];
  9 
 10 struct Node
 11 {
 12     int c,size;
 13     unsigned int v;
 14     Node *s[2],*par;
 15     Node()
 16     {
 17         c=size=0;
 18         v=0;
 19     }    
 20 };
 21 
 22 struct splay
 23 {
 24     Node t[maxn],null;
 25     Node *root;
 26     int ne;
 27     
 28     splay()
 29     {
 30         null.s[0]=null.s[1]=null.par=&null;
 31         t[0].s[0]=&null,t[0].s[1]=&t[1],t[0].par=&null,t[0].size=2,t[0].c=0,t[0].v=0;
 32         t[1].s[0]=&null,t[1].s[1]=&null,t[1].par=&t[0],t[1].size=1,t[1].c=0,t[1].v=0;
 33         root=&t[0];
 34         ne=2;
 35     }
 36 
 37     void travel(Node* now)
 38     {
 39         if (now->s[0] != &null)
 40             travel(now->s[0]);
 41         printf("%c",now->c+'a'-1);
 42         if (now->s[1] != &null)
 43             travel(now->s[1]);
 44     }
 45 
 46     inline void _update(Node* now)
 47     {
 48         now->size=now->s[0]->size+now->s[1]->size+1;
 49         now->v=now->s[0]->v+now->c*hash[now->s[0]->size]+now->s[1]->v*hash[now->s[0]->size+1];
 50     }
 51 
 52     inline void _rot(Node* now,int l)
 53     {
 54         int r=!l;
 55         Node* s=now->s[l];
 56         Node* p=now->par;
 57         (now->s[l]=s->s[r])->par=now;
 58         (s->s[r]=now)->par=s;
 59         s->par=p;
 60         if (p != &null)
 61             p->s[now == p->s[1]]=s;
 62         _update(now);
 63         _update(s);
 64     }
 65 
 66     inline void _splay(Node* now,Node* goal)
 67     {
 68         while (now->par != goal)
 69         {
 70             Node* p=now->par;
 71             Node* g=p->par;
 72             bool dp=now == p->s[1];
 73             bool dg=p == g->s[1];
 74             if (g == goal)
 75             {
 76                 _rot(p,dp);
 77                 break;
 78             }
 79             if (dp == dg)
 80             {
 81                 _rot(g,dg);
 82                 _rot(p,dp);
 83             }
 84             else
 85             {
 86                 _rot(p,dp);
 87                 _rot(g,dg);
 88             }
 89         }
 90         if (goal == &null)
 91             root=now;
 92     }
 93 
 94     inline Node* _select(int v)
 95     {
 96         Node* now=root;
 97         while (1)
 98         {
 99             if (now == &null)
100                 return now;
101             if (now->s[0]->size+1 == v)
102                 return now;
103             if (v <= now->s[0]->size)
104                 now=now->s[0];
105             else
106             {
107                 v-=now->s[0]->size+1;
108                 now=now->s[1];
109             }
110         }
111     }
112 
113     inline void change(int pos,char ch)
114     {
115         Node* p=_select(pos);
116         _splay(p,&null);
117         p->c=ch-'a'+1;
118         _update(p);
119     }
120 
121     inline void insert(int pos,char ch)
122     {
123         Node* p=_select(pos);
124         Node* q=_select(pos+1);
125         _splay(p,&null);
126         _splay(q,root);
127         (q->s[0]=&t[ne++])->par=q;
128         Node* now=q->s[0];
129         now->s[0]=now->s[1]=&null;
130         now->c=ch-'a'+1;
131         now->size=1;
132         now->v=ch-'a'+1;
133         _update(q);
134         _update(p);
135     }
136 
137     inline bool check(int x,int y,int len)
138     {
139         Node* p=_select(x);
140         Node* q=_select(x+len+1);
141         _splay(p,&null);
142         _splay(q,root);
143         unsigned int ans=q->s[0]->v;
144         p=_select(y);
145         q=_select(y+len+1);
146         _splay(p,&null);
147         _splay(q,root);
148         return q->s[0]->v == ans;
149     }
150 
151     inline int query(int x,int y)
152     {
153         int len=root->size;
154         if (x == y)
155             return len-x-1;
156         Node* p=_select(x+1);
157         Node* q=_select(y+1);
158         if (p->c != q->c)
159             return 0;
160         int l=1,r=len-y,ans=0;
161         while (l < r)
162         {
163             int mid=(l+r)>>1;
164             if (check(x,y,mid))
165             {
166                 ans=mid;
167                 l=mid+1;
168             }
169             else
170                 r=mid;
171         }
172         return ans;
173     }
174 }t;
175 
176 int main()
177 {
178     //freopen("1.in","r",stdin);
179     //freopen("1.out","w",stdout);
180     int _,x,y;
181     char ch[2],s[2];
182     char st[maxn];
183     scanf("%s",st);
184     hash[0]=1;
185     for (int i=1;i<=maxn;i++)
186         hash[i]=hash[i-1] * mod;
187     int len=strlen(st);
188     for (int i=0;i<len;i++)
189         t.insert(i+1,st[i]);
190     scanf("%d",&_);
191     while (_--)
192     {
193         scanf("%s",ch);
194         if (ch[0] == 'Q')
195         {
196             scanf("%d%d",&x,&y);
197             if (x > y)
198                 x^=y^=x^=y;
199             printf("%d\n",t.query(x,y));
200         }
201         if (ch[0] == 'R')
202         {
203             scanf("%d%s",&x,s);
204             t.change(x+1,s[0]);
205         }
206         if (ch[0] == 'I')
207         {
208             scanf("%d%s",&x,s);
209             t.insert(x+1,s[0]);
210         }
211     }
212     return 0;
213 }

嗯，好像本弱刷了那么久也就这么几道。。。

最后

sro zhx orz

sro huge brusher crf orz

sro psq orz

sro wzy orz

sro __ty orz

sro dby orz

pyfissb