解题：洛谷4230 连环病原体

(现已加入车万题目豪华套餐)

写完才知道LCT在Getroot之后不Splay会被卡，感谢良心出题人

三合一好题，LCT+双指针+差分。用LCT维护连通性，双指针每次在$[l,r]$出环时会对$[l,r]$产生$n-r+1$的贡献，对$[r+1,n]$产生一个首项为$n-r$公差为$1$的等差数列的贡献，差分两次即可

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=200005;
  6 int son[N][2],fth[N],rev[N],stk[N];
  7 int xx[N],yy[N];long long dif[N];
  8 int n,lp,rp,top;
  9 void Release(int nde)
 10 {
 11     if(rev[nde])
 12     {
 13         int &lson=son[nde][0],&rson=son[nde][1];
 14         rev[lson]^=1,rev[rson]^=1,rev[nde]^=1;
 15         swap(lson,rson);
 16     }
 17 }
 18 bool Nottop(int nde)
 19 {
 20     int fa=fth[nde];
 21     return son[fa][0]==nde||son[fa][1]==nde;
 22 }
 23 void Rotate(int nde)
 24 {
 25     int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][0];
 26     if(Nottop(fa)) son[gr][fa==son[gr][1]]=nde;
 27     fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa;
 28     son[fa][isl^1]=son[nde][isl],son[nde][isl]=fa;
 29 }
 30 void Splay(int nde)
 31 {
 32     stk[top=1]=nde;
 33     for(int i=nde;Nottop(i);i=fth[i])
 34         stk[++top]=fth[i];
 35     while(top) Release(stk[top--]);
 36     while(Nottop(nde))
 37     {
 38         int fa=fth[nde],gr=fth[fa];
 39         if(Nottop(fa))
 40             Rotate(((son[fa][0]==nde)==(son[gr][0]==fa))?fa:nde);
 41         Rotate(nde);
 42     }
 43 }
 44 void Access(int nde)
 45 {
 46     int mem=nde,lst=0;
 47     while(nde)
 48     {
 49         Splay(nde),son[nde][1]=lst;
 50         lst=nde,nde=fth[nde];
 51     }
 52     Splay(mem);
 53 }
 54 void Turnroot(int nde)
 55 {
 56     Access(nde),rev[nde]^=1;
 57 }
 58 void Split(int x,int y)
 59 {
 60     Turnroot(x),Access(y);
 61 }
 62 int Getroot(int nde)
 63 {
 64     Access(nde);
 65     while(son[nde][0])
 66         nde=son[nde][0];
 67     Splay(nde);
 68     return nde;
 69 }
 70 void Link(int x,int y)
 71 {
 72     Turnroot(x),fth[x]=y;
 73 }
 74 void Cut(int x,int y)
 75 {
 76     Split(x,y);
 77     fth[x]=son[y][0]=0;
 78 }
 79 bool Ring(int p)
 80 {
 81     Turnroot(xx[p]);
 82     return Getroot(yy[p])==xx[p];
 83 }
 84 void Add(int l,int r,int b,int p)
 85 {
 86     int e=b+(r-l)*p;
 87     dif[l]+=b,dif[l+1]+=p-b;
 88     dif[r+1]-=e+p,dif[r+2]+=e;
 89 }
 90 int main()
 91 {
 92     scanf("%d",&n);
 93     for(int i=1;i<=n;i++)
 94         scanf("%d%d",&xx[i],&yy[i]);
 95     lp=1,rp=2,Link(xx[1],yy[1]),xx[n+1]=1,yy[n+1]=n+1;
 96     while(lp<=n&&rp<=n)
 97     {
 98         while(!Ring(rp)&&rp<=n) 
 99             Link(xx[rp],yy[rp]),rp++;
100         if(Ring(rp))
101         {
102             Add(lp,rp,n-rp+1,0);
103             Add(rp+1,n,n-rp,-1);
104             if(rp==n) break;
105         }
106         Cut(xx[lp],yy[lp]),lp++;
107     }
108     for(int i=1;i<=n;i++) dif[i]+=dif[i-1];
109     for(int i=1;i<=n;i++) dif[i]+=dif[i-1];
110     for(int i=1;i<=n;i++) printf("%lld ",dif[i]);
111     return 0;
112 }

View Code