指针版P3690 【模板】Link Cut Tree （动态树）

小鱼儿 2021-12-23 05:47 114阅读 0赞

## 题面 ##

[传送门][Link 1]

## 题解 ##

鉴于数组版实在是太慢我用指针版重新写了一遍

代码基本是借鉴了lxl某道关于\\(LCT\\)的题

//minamoto #include<bits/stdc++.h> #define R register #define inline __inline__ __attribute__((always_inline)) #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } inline int getop(){R char ch;while((ch=getc())>'9'||ch<'0');return ch-'0';} char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(R int x){ if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=3e5+5; struct node;typedef node* ptr; inline void swap(R ptr &x,R ptr &y){R ptr t=x;x=y,y=t;} struct node{ ptr lc,rc,fa;int s,v,r; inline node(); inline void ppd(){swap(lc,rc),r^=1;} inline void pd(){if(r)lc->ppd(),rc->ppd(),r=0;} inline ptr upd(){return s=lc->s^rc->s^v,this;} }e[N]; inline node::node(){fa=lc=rc=e;} inline bool isrt(R ptr p){return p->fa->lc!=p&&p->fa->rc!=p;} void rotate(ptr p){ ptr s=p->fa,t=s->fa; if(!isrt(s))(t->lc==s?t->lc:t->rc)=p; p->fa=t,s->fa=p; if(s->lc==p)s->lc=p->rc,p->rc->fa=s,p->rc=s->upd(); else s->rc=p->lc,p->lc->fa=s,p->lc=s->upd(); } void push(ptr p){if(!isrt(p))push(p->fa);p->pd();} ptr splay(ptr p){ push(p); while(!isrt(p)){ if(!isrt(p->fa))rotate(p->fa->lc==p^p->fa->fa->lc==p->fa?p:p->fa); rotate(p); } return p->upd(); } ptr exp(ptr p){ ptr s=e; while(p!=e)splay(p)->rc=s,s=p->upd(),p=p->fa; return s; } inline void makert(ptr p){exp(p),splay(p)->ppd();} inline ptr split(ptr s,ptr t){return makert(s),exp(t);} ptr findrt(ptr p){ exp(p),splay(p)->pd(); while(p->lc!=e)(p=p->lc)->pd(); return p; } void link(ptr s,ptr t){ makert(s); if(findrt(t)!=s)s->fa=t; //虚儿子接上之后根本不用upd } void cut(ptr s,ptr t){ makert(s); if(findrt(t)==s&&s->fa==t&&s->rc==e) s->fa=t->lc=e,t->upd(); } int n,m,op,u,v; int main(){ // freopen("testdata.in","r",stdin); // freopen("testdata.out","w",stdout); n=read(),m=read(); fp(i,1,n)(e+i)->v=read(),(e+i)->upd(); while(m--){ op=getop(),u=read(),v=read(); switch(op){ case 0:print(split(e+u,e+v)->s);break; case 1:link(e+u,e+v);break; case 2:cut(e+u,e+v);break; case 3:splay(e+u),(e+u)->v=v,(e+u)->upd();break; } } return Ot(),0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10714675.html

[Link 1]: https://www.luogu.org/problemnew/show/P3690