摘要:尺取法动态树判环

luogu4230连环病原体

题面

题目分析

尺取法应该是很显然的,一个区间内包含环后,后面的边继续加入也依旧满足条件,所以可以直接对于一个固定的$l$去寻找第一个成环的位置$r$,而$l$的顺次增大会导致减少一条边,满足条件的$r$只会不动或者向后移.

考虑位置$l$与第一个成环的位置$r$对答案的贡献,举个例子就很直观,设$m=8,l=1,r=2$:

ans:7 7 6 5 4 3 2 1

除开$[1,2]$内均为$m-r+1$,ans:0 0 6 5 4 3 2 1

差分一次:0 0 6 -1 -1 -1 -1 -1

差分两次:0 0 6 -7 0 0 0 0

容易发现贡献是一个常序列并上一个公差为$1$的等差数列,对等差数列差分两次后就成了单点修改,在处理完之后进行一遍前缀和还原,再加上所有常数列的差分,再进行一次前缀和还原即得答案.

判环使用lct实现的动态树就好了,每次加入$r$时,如果发现两端的点已经连通就说明加入这条边会成环于是找到了第一个位置$r$,其他的细节看代码吧.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=400010;
lxl n,m,NodeCnt,l,r,con,SegCnt;
lxl c[2][big],fa[big],tag[big],q[big],d[big];
struct _Edge
{
lxl u,v;
}e[big];
struct _Seg
{
lxl l,r,val;
}s[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void PushDown(lxl x)
{
if(!tag[x])return;
lxl &l=c[0][x],&r=c[1][x];
tag[l]=tag[l]^1,tag[r]=tag[r]^1,tag[x]=tag[x]^1;
std::swap(l,r);
}
inline bool IsRoot(lxl x){return c[0][fa[x]]!=x&&c[1][fa[x]]!=x;}
inline void rotate(lxl x)
{
lxl y=fa[x],z=fa[y],d=c[1][y]==x;
if(!IsRoot(y))c[c[1][z]==y][z]=x;
fa[x]=z,fa[y]=x,fa[c[d^1][x]]=y;
c[d][y]=c[d^1][x],c[d^1][x]=y;
}
inline void splay(lxl x)
{
q[q[0]=1]=x;for(R int i(x);!IsRoot(i);i=fa[i])q[++q[0]]=fa[i];
for(R int i(q[0]);i;--i)PushDown(q[i]);
while(!IsRoot(x))
{
lxl y=fa[x],z=fa[y];
if(!IsRoot(fa[x]))rotate((c[0][y]==x)^(c[0][z]==y)?x:y);
rotate(x);
}
}
inline void access(lxl x){for(R int t(0);x;t=x,x=fa[x])splay(x),c[1][x]=t;}
inline void MakeRoot(lxl x){access(x),splay(x),tag[x]^=1;}
inline lxl FindRoot(lxl x)
{
access(x),splay(x);
while(c[0][x])PushDown(x),x=c[0][x];splay(x);
return x;
}
inline void cut(lxl x,lxl y)
{
MakeRoot(x);
if(FindRoot(y)!=x||fa[y]!=x||c[0][y])return;
fa[y]=c[1][x]=0;
}
inline bool link(lxl x,lxl y)
{
MakeRoot(x);
if(FindRoot(y)==x)return true;
fa[x]=y;return false;
}
int main(void)
{
m=read();
for(R int i(1);i<=m;++i)e[i]=(_Edge){read(),read()};
l=r=1;
while(l<=m)
{
con=link(e[r].u,e[r].v);
// if(l==3)debug(r),debug(con);
while((!con)&&r<m)++r,con=link(e[r].u,e[r].v);
// ,debug(l),debug(r),debugi(con),endl;
if(con)s[++SegCnt]={l,r,m-r+1},d[r+1]+=m-r,d[r+2]+=-(m-r+1);
// ,debug(l),debug(r),endl;
cut(e[l].u,e[l].v),++l,con=0;
if(r==m&&!con)break;
}
for(R int i(1);i<=m;++i)d[i]+=d[i-1];
// for(R int i(1);i<=m;++i)debug(d[i]);
// debug(SegCnt);
for(R int i(1);i<=SegCnt;++i)d[s[i].l]+=s[i].val,d[s[i].r+1]-=s[i].val;
for(R int i(1);i<=m;++i)d[i]+=d[i-1];
for(R int i(1);i<=m;++i)printf("%lld ",d[i]);endl;
return 0;
}
/*
6
1 2
1 10
5 6
6 5
1 7
1 8
*/