第一次做交互题,感觉挺有趣的.
这道题链的部分还挺好想的.
然后树的部分就轻重链剖分后在链上二分拐点就好了.
动态轻重链剖分用 LCT 来维护.
code:
#include "rts.h" #include <bits/stdc++.h> #define N 1000005 #define ll long long #define lson s[x].ch[0] #define rson s[x].ch[1] using namespace std; int vis[N],arr[N],sta[N]; int ran(int l) { return (ll)rand()*rand()%l+1; } struct data { int ch[2],f,rev,l,r; }s[N]; inline int get(int x) { return s[s[x].f].ch[1]==x; } inline int isr(int x) { return s[s[x].f].ch[0]!=x&&s[s[x].f].ch[1]!=x; } inline void pushup(int x) { s[x].l=s[x].r=x; if(lson) s[x].l=s[lson].l; if(rson) s[x].r=s[rson].r; } inline void mark(int x) { s[x].rev^=1,swap(lson,rson),swap(s[x].l,s[x].r); } inline void push(int x) { if(s[x].rev) { if(lson) mark(lson); if(rson) mark(rson); s[x].rev^=1; } } void rotate(int x) { int old=s[x].f,fold=s[old].f,which=get(x); if(!isr(old)) s[fold].ch[s[fold].ch[1]==old]=x; s[old].ch[which]=s[x].ch[which^1]; if(s[old].ch[which]) s[s[old].ch[which]].f=old; s[x].ch[which^1]=old,s[old].f=x,s[x].f=fold; pushup(old),pushup(x); } void splay(int x) { int v=0,u=x,fa; for(sta[++v]=u;!isr(u);u=s[u].f) sta[++v]=s[u].f; for(;v;--v) push(sta[v]); for(u=s[u].f;(fa=s[x].f)!=u;rotate(x)) if(s[fa].f!=u) rotate(get(fa)==get(x)?fa:x); } void access(int x) { for(int y=0;x;y=x,x=s[x].f) splay(x),rson=y,pushup(x); } void makert(int x) { access(x),splay(x),mark(x); } void link(int x,int y) { s[x].f=y; } int getrt(int x) { while(!isr(x)) x=s[x].f; return x; } void play(int n, int T, int dataType) { srand((unsigned)time(NULL)); if(dataType==3) { int L=1,R=1; for(int i=2;i<=n;++i) arr[i]=i; random_shuffle(arr+2,arr+1+n); for(int i=2;i<=n;++i) { int u=arr[i]; if(vis[u]) continue; int p=explore(L,u); if(!vis[p]) { vis[p]=1,L=p; while(p!=u) p=explore(p,u),L=p,vis[p]=1; } else { int p2=explore(R,u); vis[p2]=1,R=p2; while(p2!=u) p2=explore(p2,u),R=p2,vis[p2]=1; } } } else { vis[1]=1,arr[1]=1; for(int i=2;i<=n;++i) arr[i]=i; random_shuffle(arr+2,arr+1+n); for(int i=2;i<=n;++i) { int u=arr[i]; if(vis[u]) continue; int x=getrt(1),cn=0; while(1) { push(x); int cur=explore(x,u); if(!vis[cur]) { vis[cur]=1,link(cur,x),x=cur; while(cur!=u) { cur=explore(cur,u); vis[cur]=1,link(cur,x),x=cur; } access(x); break; } if(cur==s[rson].l) x=rson; else if(cur==s[lson].r) x=lson; else x=getrt(cur); } } } }