LCT练习题
第一次用指针打LCT，有蛮多意外的，不过确实感觉指针比数组打起来爽多了
#include <cstdio>#include <iostream>#include <algorithm>#define N 100010using namespace std;int n,m,x,y,tp,f[N],tot[N],G[N];char op;struct lef{ lef *fa,*ch[2]; int sz,isz,rev;}PR[N],*A[N],*sta[N];struct edge{ int t,nx;}E[N];inline void reaD(int &x){ char Ch=getchar();x=0; for(;Ch>'9'||Ch<'0';Ch=getchar()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=getchar());}int fifa(int x){return f[x]==x?x:f[x]=fifa(f[x]);}inline int isl(lef *x){return x->fa&&x->fa->ch[1]==x;}inline int isr(lef *x){return !x->fa||(x->fa->ch[0]!=x&&x->fa->ch[1]!=x);}inline void updat(lef *x){ if(!x) return; x->sz=x->isz+1; if(x->ch[0]) x->sz+=x->ch[0]->sz; if(x->ch[1]) x->sz+=x->ch[1]->sz;}inline void pushdn(lef *x){ if(!(x&&x->rev)) return; swap(x->ch[0],x->ch[1]); if(x->ch[0]) x->ch[0]->rev^=1; if(x->ch[1]) x->ch[1]->rev^=1; x->rev=0;}inline void rot(lef *x){ lef *y=x->fa,*z=y->fa; int lor=isl(x); if(!isr(y)) z->ch[z->ch[1]==y]=x; x->fa=z; if(y->ch[lor]=x->ch[lor^1]) y->ch[lor]->fa=y; (x->ch[lor^1]=y)->fa=x; updat(y); updat(x);}inline void splay(lef *x){ sta[tp=1]=x; for(lef *i=x;!isr(i);i=i->fa) sta[++tp]=i->fa; for(;tp;--tp) pushdn(sta[tp]); for(;!isr(x);rot(x)) if(!isr(x->fa)) rot(isl(x)^isl(x->fa)?x:x->fa);}inline void access(lef *x){ lef *t=0; for(;x;x=x->fa){ splay(x); if(x->ch[1]) x->isz+=x->ch[1]->sz; if(t) x->isz-=t->sz; x->ch[1]=t; t=x; updat(x); }}inline void reverse(lef *x){ access(x); splay(x); x->rev^=1;}inline void link(lef *x,lef *y){ reverse(y); reverse(x); x->fa=y; y->isz+=x->sz; updat(y); access(x);}int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); reaD(n);reaD(m); for(int i=1;i<=n;i++) A[i]=&pr[i],A[i]->sz=1,tot[i]=1,f[i]=i; for(int i=1;i<=m;i++){ while((op=getchar())!='A'&&op!='Q'); if(op=='A'){ reaD(x); reaD(y); tot[fifa(y)]+=tot[fifa(x)]; f[fifa(x)]=fifa(y); link(A[x],A[y]); } else{ reaD(x);reaD(y); reverse(A[x]); access(A[y]); splay(A[x]); printf("%d/n",(A[y]->sz)*(A[x]->sz-A[y]->sz)); } }}新闻热点
疑难解答
