[补]联合省选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]);
}