[补]联合省选2021 图函数

Posted on Edited on In

[补]联合省选2021 图函数

考虑将所有加入 \(i-m\) 这些边的答案一起算出来

模拟删去点的过程容易发现，删去 \(u\) 时， \(u,v\) 在同一个强连通分量里的点满足：

存在仅包含 \(\ge u\) 的点的路径，使得 \(u,v\) 互相连通

设 \(A_{u,v}\) 表示最大的 \(i\) 使得 \(u\) 能仅通过 \(\ge u\) 的点到达 \(v\)

设 \(B_{u,v}\) 表示最大的 \(i\) 使得 \(v\) 能仅通过 \(\ge u\) 的点到达 \(u\)

计算 \(\min\{A_{u,v},B_{u,v}\}\) 即可确定一个点对能够贡献到的区间

考虑依次加入每一条边 \((u,v)\) ，在正反图上计算 \(A,B\) 中每个元素第一次被确定的时间

以计算 \(A\) 为例，每次会被更新的 \(A_{i,..}\) 一定满足

\(i\ge \min\{u,v\},i\rightarrow u,i\not \rightarrow v\)

可以暴力 \(\text{for}\) 这样的 \(i\) ，从 \([i,v]\) 开始，让 \(v\) 扩展，每次扩展找到未确定的 \([i,w]\)

每个元素只会被确定一次，复杂度为 \(O(n^2)\) ，暴力枚举起点为 \(O(nm)\)

可以用 \(\text{bitset}\) 优化到 \(O(\frac{nm}{64}+n^2)\) (扩展元素的部分复杂度可能是假的，但是没有关系)

Loj Submission

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
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
using ull=unsigned long long;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
int rd(){
	int s=0; static char c;
	while(c=getchar(),c<48);
	do s=(s<<1)+(s<<3)+(c^'0');
	while(c=getchar(),c>47);
	return s;
}
enum{N=1010,M=200010};
int n,m,t;
int A[N][N],B[N][N],U[M],V[M],ans[M];
int Log(ull x){ return !x?-1:__builtin_ctzll(x); }
struct Bitset{
	ull a[16];
	void turn(int x){ a[x>>6]^=1ull<<x; }
} X[N],Y[N];
vector <int> G[N],E[N];
void dfs1(int st,int u) {
	if(~A[st][u]) return;
	A[st][u]=t,X[u].turn(st);
	for(int v:G[u]) if(v>=st) dfs1(st,v);
}
void dfs2(int st,int u) {
	if(~B[st][u]) return;
	B[st][u]=t,Y[u].turn(st);
	for(int v:E[u]) if(v>=st) dfs2(st,v);
}

int main(){
	n=rd(),m=rd();
	rep(i,0,m-1) U[i]=rd(),V[i]=rd();
	memset(A,-1,sizeof A),memset(B,-1,sizeof B);
	rep(i,1,n) A[i][i]=B[i][i]=m,X[i].turn(i),Y[i].turn(i);
	for(t=m-1;~t;t--) {
		G[U[t]].pb(V[t]),E[V[t]].pb(U[t]);
		int L=min(U[t],V[t]);
		rep(i,0,L>>6) {
            // bitset 优化。
			for(int j;~(j=Log(X[U[t]].a[i]&~X[V[t]].a[i])) && (i<<6|j)<=L;) dfs1(i<<6|j,V[t]);
			for(int j;~(j=Log(Y[V[t]].a[i]&~Y[U[t]].a[i])) && (i<<6|j)<=L;) dfs2(i<<6|j,U[t]);
		}
	}
	rep(i,1,n) rep(j,i,n) if(~A[i][j] && ~B[i][j]) ans[min(A[i][j],B[i][j])]++;
	drep(i,m,0) ans[i]+=ans[i+1];
	rep(i,0,m) printf("%d ",ans[i]);
}