[补]联合省选2021 图函数

[补]联合省选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,..})一定满足

(ige min{u,v},i ightarrow u,i ot ightarrow v)

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

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

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

Loj Submission

#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]);
}