[BZOJ 3682]Phorni

后缀平衡树的模板题? I'm so weak……

现在觉得替罪羊树比 treap 好写,是不是没救了喵~

  1 #include <cstdio>
  2 #include <cmath>
  3 typedef unsigned long long LL;
  4 const double a=0.55;
  5 const LL inf=1ULL<<63;
  6 const int sizeOfString=500005;
  7 const int sizeOfTree=2100021;
  8 
  9 inline int getint();
 10 inline char getch();
 11 inline int getstr(char * );
 12 inline void putint(int);
 13 
 14 int n, q, len, type;
 15 char s[sizeOfString];
 16 int P[sizeOfString];
 17 inline void reverse();
 18 
 19 struct node {int p, s; LL tag; node * c[2];};
 20 node memory_node[sizeOfString], * port_node=memory_node;
 21 node * root;
 22 node * suf[sizeOfString];
 23 inline node * newnode(int);
 24 inline bool cmp(int, int);
 25 inline bool cmp(node * , node * );
 26 node * flatten(node * , node * );
 27 node * build(node * , int);
 28 void print(node * );
 29 void rebuild(node *& );
 30 void remark(node * , LL, LL);
 31 bool insert(node *& , node * , LL=1, LL=inf, int=0);
 32 
 33 struct seg {int p; seg * l, * r;};
 34 seg memory_seg[sizeOfTree], * port_seg=memory_seg;
 35 seg * t;
 36 inline seg * newseg();
 37 inline int min(int, int);
 38 seg * build(int, int);
 39 void update(seg * , int, int, int);
 40 int query(seg * , int, int, int, int);
 41 
 42 int main()
 43 {
 44     int ans=0;
 45     char ch;
 46     int c, x, pos, l, r;
 47 
 48     n=getint(), q=getint(), len=getint(), type=getint();
 49     getstr(s);
 50     reverse();
 51 
 52     root=suf[0]=newnode(0);
 53     root->tag=(1+inf)>>1;
 54     for (int i=1;i<=len;i++)
 55     {
 56         suf[i]=newnode(i);
 57         insert(root, suf[i]);
 58     }
 59 
 60     for (int i=1;i<=n;i++) P[i]=getint();
 61 
 62     t=build(1, n);
 63     for (int i=1;i<=q;i++)
 64     {
 65         ch=getch();
 66         if (ch=='I')
 67         {
 68             c=getint(); if (type) c=c^ans;
 69             s[++len]=c+'a';
 70             suf[len]=newnode(len);
 71             insert(root, suf[len]);
 72         }
 73         if (ch=='C')
 74         {
 75             x=getint(); pos=getint();
 76             P[x]=pos;
 77             update(t, 1, n, x);
 78         }
 79         if (ch=='Q')
 80         {
 81             l=getint(); r=getint();
 82             ans=query(t, 1, n, l, r);
 83             putint(ans);
 84         }
 85     }
 86 
 87     return 0;
 88 }
 89 inline int getint()
 90 {
 91     register int num=0;
 92     register char ch;
 93     do ch=getchar(); while (ch<'0' || ch>'9');
 94     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
 95     return num;
 96 }
 97 inline char getch()
 98 {
 99     register char ch;
100     do ch=getchar(); while (ch!='I' && ch!='C' && ch!='Q');
101     return ch;
102 }
103 inline int getstr(char * str)
104 {
105     register int len=0;
106     register char ch;
107     do ch=getchar(); while (ch<'a' || ch>'z');
108     do str[++len]=ch, ch=getchar(); while (ch>='a' && ch<='z');
109     return len;
110 }
111 inline void putint(int num)
112 {
113     char stack[11];
114     register int top=0;
115     for ( ;num;num/=10) stack[++top]=num%10+'0';
116     for ( ;top;top--) putchar(stack[top]);
117     putchar('
');
118 }
119 inline void reverse()
120 {
121     static char t[sizeOfString];
122     for (int i=1;i<=len;i++) t[i]=s[len-i+1];
123     for (int i=1;i<=len;i++) s[i]=t[i];
124 }
125 inline node * newnode(int p)
126 {
127     node * ret=port_node++;
128     ret->p=p; ret->s=1;
129     ret->tag=0LL;
130     ret->c[0]=NULL; ret->c[1]=NULL;
131     return ret;
132 }
133 inline bool cmp(int a, int b)
134 {
135     return suf[a]->tag<suf[b]->tag;
136 }
137 inline bool cmp(node * a, node * b)
138 {
139     return s[a->p]==s[b->p]?cmp(a->p-1, b->p-1):s[a->p]<s[b->p];
140 }
141 node * flatten(node * x, node * y)
142 {
143     if (!x) return y;
144     x->c[1]=flatten(x->c[1], y);
145     return flatten(x->c[0], x);
146 }
147 node * build(node * x, int s)
148 {
149     node * y, * z;
150     if (!s) return x->c[0]=NULL, x;
151     y=build(x, s>>1); z=build(y->c[1], s-1-(s>>1));
152     y->c[1]=z->c[0]; z->c[0]=y;
153     return z;
154 }
155 void rebuild(node *& t)
156 {
157     static node temp;
158     node * line;
159     int n=t->s;
160     line=flatten(t, &temp);
161     build(line, n);
162     t=temp.c[0];
163 }
164 void remark(node * t, LL l, LL r)
165 {
166     LL m=(l+r)>>1;
167     t->tag=m; t->s=1;
168     if (t->c[0]) remark(t->c[0], l, m), t->s+=t->c[0]->s;
169     if (t->c[1]) remark(t->c[1], m, r), t->s+=t->c[1]->s;
170 }
171 bool insert(node *& t, node * x, LL l, LL r, int d)
172 {
173     LL m=(l+r)>>1;
174     bool ret=false;
175     if (!t) x->tag=m, t=x, ret=d>(log(root->s)/log(1.0/a));
176     else
177     {
178         t->s++;
179         if (cmp(t, x)) ret=insert(t->c[1], x, m, r, d+1);
180         else ret=insert(t->c[0], x, l, m, d+1);
181         if (ret) if ((t->c[0] && t->c[0]->s>a*t->s) || (t->c[1] && t->c[1]->s>a*t->s))
182         {
183             rebuild(t);
184             remark(t, l, r);
185             ret=false;
186         }
187     }
188     return ret;
189 }
190 inline seg * newseg()
191 {
192     seg * ret=port_seg++;
193     ret->l=ret->r=NULL;
194     return ret;
195 }
196 inline int min(int x, int y)
197 {
198     if (suf[P[x]]->tag<=suf[P[y]]->tag) return x;
199     return y;
200 }
201 seg * build(int l, int r)
202 {
203     seg * t=newseg();
204     if (l==r) return t->p=l, t;
205     int m=(l+r)>>1;
206     t->l=build(l, m); t->r=build(m+1, r);
207     t->p=min(t->l->p, t->r->p);
208     return t;
209 }
210 void update(seg * t, int l, int r, int p)
211 {
212     if (l==r) return ;
213     int m=(l+r)>>1;
214     if (p<=m) update(t->l, l, m, p);
215     else update(t->r, m+1, r, p);
216     t->p=min(t->l->p, t->r->p);
217 }
218 int query(seg * t, int l, int r, int ql, int qr)
219 {
220     if (l==ql && r==qr) return t->p;
221     int m=(l+r)>>1;
222     if (qr<=m) return query(t->l, l, m, ql, qr);
223     else if (ql>=m+1) return query(t->r, m+1, r, ql, qr);
224     return min(query(t->l, l, m, ql, m), query(t->r, m+1, r, m+1, qr));
225 }
又 RE 又 WA 一时爽

到最后也没有搞清楚 zkw 炸在哪里……

大概是 zkw 查询时并不是顺序的缘故?

原文地址:https://www.cnblogs.com/dyllalala/p/4140407.html