题面戳我

sol

很好想+很好写的一道题，然而比赛中我还是没有切掉qaq。

LCT

枚举左端点\(i\)，向右移动右端点指针\(j\)找到第一个成环的位置。此时\([i,j],[i,j+1]...[i,m]\)都是合法答案。可见就是在区间\([i,j]\)上区间加\(m-j+1\)，再在\([j+1,m]\)上加上一个等差数列\(m-j,m-j-1...1\)

等差数列直接二阶差分最后做两次前缀和即可。

以下内容摘自出题人题解

时间复杂度O(nlogn) ，期望得分100分，实际得分75~100分

FAQ：为什么我写了LCT却只得了75分/90分

A：因为findroot后要splay才能保证复杂度，不splay的都被我卡到O(n^2)啦！

发现自己以前写的LCT从来没有在findroot后splay。细思极恐。

code

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 1000005;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

int m,u[N],v[N],o[N<<1],fa[N],ch[2][N],rev[N],Stack[N],top,t1[N],t2[N];

bool son(int x){return x==ch[1][fa[x]];}

bool isroot(int x){return x!=ch[0][fa[x]]&&x!=ch[1][fa[x]];}

void reverse(int x){if(!x)return;swap(ch[0][x],ch[1][x]);rev[x]^=1;}

void pushdown(int x){if(!rev[x])return;reverse(ch[0][x]);reverse(ch[1][x]);rev[x]=0;}

void rotate(int x)

{

	int y=fa[x],z=fa[y],c=son(x);

	ch[c][y]=ch[c^1][x];if (ch[c][y]) fa[ch[c][y]]=y;

	fa[x]=z;if (!isroot(y)) ch[son(y)][z]=x;

	ch[c^1][x]=y;fa[y]=x;

}

void splay(int x)

{

	Stack[top=1]=x;

	for (int y=x;!isroot(y);y=fa[y]) Stack[++top]=fa[y];

	while (top) pushdown(Stack[top--]);

	for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])

		if (!isroot(y)) son(x)^son(y)?rotate(x):rotate(y);

}

void access(int x){for (int y=0;x;y=x,x=fa[x]) splay(x),ch[1][x]=y;}

void makeroot(int x){access(x);splay(x);reverse(x);}

int findroot(int x){access(x);splay(x);while(ch[0][x])x=ch[0][x];splay(x);return x;}

void split(int x,int y){makeroot(x);access(y);splay(y);}

void link(int x,int y){makeroot(x);fa[x]=y;}

void cut(int x,int y){split(x,y);ch[0][y]=fa[x]=0;}

int main()

{

	m=gi();

	for (int i=1;i<=m;++i) u[i]=gi(),v[i]=gi();

	for (int i=1,j=1;i<=m;cut(u[i],v[i]),++i)

	{

		while (j<=m&&findroot(u[j])!=findroot(v[j])) link(u[j],v[j]),++j;

		if (j<=m) t1[i]+=m-j+1,t2[j+1]--;

	}

	for (int i=1;i<=m;++i) t2[i]+=t2[i-1];

	for (int i=1;i<=m;++i) t1[i]+=t1[i-1],t2[i]+=t2[i-1];

	for (int i=1;i<=m;++i) printf("%d ",t1[i]+t2[i]);

	return 0;

}