[BZOJ 3123]森林

这题和 COT1 一定有 JQ 喵~

线段树的启发式合并,每次要连接两个点时就对比较小的那棵树暴力 DFS 一边

然后均摊时间依旧是 logn 的,均摊真是世界上最邪恶的东西了……

然后这题的数据是要卖萌么?!
testcase 的存在意义是被阿卡林噎掉了么?!

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 const int sizeOfPoint=100001;
  5 const int sizeOfEdge=200002;
  6 const int sizeOfNode=20000002;
  7 
  8 inline int lg(int);
  9 inline void swap(int & , int & );
 10 inline char getch();
 11 inline int getint();
 12 inline void putint(int);
 13 
 14 struct edge {int point; edge * next;};
 15 edge memory_edge[sizeOfEdge], * port_edge=memory_edge;
 16 inline edge * newedge(int, edge * );
 17 inline void link(int, int);
 18 
 19 struct node {int c; node * l , * r; inline node();};
 20 node * null=new node();
 21 node memory_node[sizeOfNode], * port_node=memory_node;
 22 inline node * newnode(node * =null);
 23 node * insert(node * , int, int, int);
 24 
 25 int b[sizeOfPoint], s[sizeOfPoint];
 26 int find(int);
 27 inline void merge(int, int);
 28 
 29 int testcase;
 30 int N, M, T, U;
 31 int p[sizeOfPoint], q[sizeOfPoint];
 32 int f[sizeOfPoint], d[sizeOfPoint], a[32][sizeOfPoint];
 33 edge * e[sizeOfPoint];
 34 node * t[sizeOfPoint];
 35 inline void clear();
 36 inline bool cmp(int, int);
 37 inline void discretization();
 38 void dfs(int);
 39 inline int lca(int, int);
 40 inline int query(int, int, int);
 41 
 42 int main()
 43 {
 44     int lastans=0;
 45 
 46     testcase=getint();
 47     for (testcase=1;testcase;testcase--)
 48     {
 49         N=getint(), M=getint(), T=getint();
 50         clear();
 51         for (int i=1;i<=N;i++)
 52             p[i]=getint();
 53         for (int i=1;i<=M;i++)
 54         {
 55             int u=getint(), v=getint();
 56             link(u, v);
 57         }
 58         discretization();
 59 
 60         for (int i=1;i<=N;i++) if (f[i]==-1)
 61         {
 62             f[i]=0; d[i]=0;
 63             dfs(i);
 64         }
 65 
 66         for (int i=1;i<=T;i++)
 67         {
 68             char c=getch(); int x=getint()^lastans, y=getint()^lastans;
 69             if (c=='Q')
 70             {
 71                 int k=getint()^lastans;
 72                 lastans=query(x, y, k);
 73                 putint(lastans);
 74             }
 75             else
 76             {
 77                 int bx=find(x), by=find(y);
 78                 if (bx==by) continue;
 79                 if (s[bx]<s[by]) swap(x, y);
 80                 link(x, y);
 81                 f[y]=x; d[y]=d[x]+1;
 82                 dfs(y);
 83             }
 84         }
 85     }
 86 
 87     return 0;
 88 }
 89 
 90 inline int lg(int x)
 91 {
 92     return 31-__builtin_clz(x);
 93 }
 94 inline void swap(int & x, int & y)
 95 {
 96     int z=x;
 97         x=y;
 98         y=z;
 99 }
100 inline char getch()
101 {
102     register char ch;
103     do ch=getchar(); while (ch!='L' && ch!='Q');
104     return ch;
105 }
106 inline int getint()
107 {
108     register int num=0;
109     register char ch=0, last;
110     do last=ch, ch=getchar(); while (ch<'0' || ch>'9');
111     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
112     if (last=='-') num=-num;
113     return num;
114 }
115 inline void putint(int num)
116 {
117     char stack[11];
118     register int top=0;
119     if (num==0) stack[top=1]='0';
120     if (num<0) putchar('-'), num=-num;
121     for ( ;num;num/=10) stack[++top]=num%10+'0';
122     for ( ;top;top--) putchar(stack[top]);
123     putchar('
');
124 }
125 
126 inline edge * newedge(int point, edge * next)
127 {
128     edge * ret=port_edge++;
129     ret->point=point; ret->next=next;
130     return ret;
131 }
132 inline void link(int u, int v)
133 {
134     e[u]=newedge(v, e[u]);
135     e[v]=newedge(u, e[v]);
136     merge(u, v);
137 }
138 
139 inline node::node()
140 {
141     this->c=0;
142     this->l=this;
143     this->r=this;
144 }
145 inline node * newnode(node * t)
146 {
147     node * newt=port_node++;
148     *newt=*t;
149     return newt;
150 }
151 node * insert(node * t, int l, int r, int k)
152 {
153     t=newnode(t);
154     t->c++;
155     if (l==r) return t;
156 
157     int m=(l+r)>>1;
158     if (k<=m) t->l=insert(t->l, l, m, k);
159     else t->r=insert(t->r, m+1, r, k);
160     return t;
161 }
162 
163 int find(int u)
164 {
165     return !b[u]?u:b[u]=find(b[u]);
166 }
167 inline void merge(int u, int v)
168 {
169     u=find(u); v=find(v);
170     b[v]=u; s[u]+=s[v];
171 }
172 
173 inline void clear()
174 {
175     port_edge=memory_edge;
176     memset(e, 0, sizeof(e));
177     port_node=memory_node;
178     for (int i=0;i<=N;i++) t[i]=null;
179     memset(f, -1, sizeof(f));
180     memset(d, -1, sizeof(d));
181     memset(b, 0, sizeof(b));
182     memset(a, 0, sizeof(a));
183     for (int i=1;i<=N;i++) s[i]=1;
184 }
185 inline bool cmp(int a, int b)
186 {
187     return p[a]<p[b];
188 }
189 inline void discretization()
190 {
191     static int k[sizeOfPoint];
192 
193     for (int i=1;i<=N;i++) k[i]=i;
194     std::sort(k+1, k+N+1, cmp);
195 
196     q[U=1]=p[k[1]]; p[k[1]]=1;
197     for (int i=2;i<=N;i++)
198     {
199         if (p[k[i]]>q[U]) q[++U]=p[k[i]];
200         p[k[i]]=U;
201     }
202 }
203 void dfs(int u)
204 {
205     t[u]=insert(t[f[u]], 1, U, p[u]);
206     if (d[u]>0)
207     {
208         int lim=lg(d[u]);
209         a[0][u]=f[u];
210         for (int i=1;i<=lim;i++)
211             a[i][u]=a[i-1][a[i-1][u]];
212         for (int i=lim+1;i<31;i++)
213             a[i][u]=0;
214     }
215 
216     for (edge * i=e[u];i;i=i->next) if (i->point!=f[u])
217     {
218         f[i->point]=u;
219         d[i->point]=d[u]+1;
220         dfs(i->point);
221     }
222 }
223 inline int lca(int u, int v)
224 {
225     if (d[u]<d[v]) swap(u, v);
226     while (int dist=d[u]-d[v]) u=a[__builtin_ctz(dist)][u];
227     if (u==v) return u;
228     for (int i=31;i>=0;i--)
229         if (a[i][u]!=a[i][v])
230             u=a[i][u],
231             v=a[i][v];
232     return f[u];
233 }
234 inline int query(int a, int b, int k)
235 {
236     int c=lca(a, b), d=f[c];
237     node * ta=t[a], * tb=t[b], * tc=t[c], * td=t[d];
238     int l=1, r=U, m;
239 
240     for ( ;l<r; )
241     {
242         m=(l+r)>>1;
243         if (ta->l->c+tb->l->c-tc->l->c-td->l->c>=k)
244         {
245             ta=ta->l; tb=tb->l; tc=tc->l; td=td->l;
246             r=m;
247         }
248         else
249         {
250             k-=ta->l->c+tb->l->c-tc->l->c-td->l->c;
251             ta=ta->r; tb=tb->r; tc=tc->r; td=td->r;
252             l=m+1;
253         }
254     }
255 
256     return q[l];
257 }
又 R 又 T 一时爽
原文地址:https://www.cnblogs.com/dyllalala/p/4165717.html