【XIV Open Cup E.V. Pankratiev. GP of SPb. H】Reachability 题解

题目大意

  一幅有向图有 $n$ 个结点，初始没有边。
  有 $q$ 个操作，四种类型：

• $+\ o\ v\ k\ a_1\ \cdots\ a_k$：加入边 $(v,a_1),\cdots,(v,a_k)$
• $+\ i\ v\ k\ a_1\ \cdots\ a_k$：加入边 $(a_1,v),\cdots,(a_k,v)$
• $-\ o\ v\ k\ a_1\ \cdots\ a_k$：删除边 $(v,a_1),\cdots,(v,a_k)$
• $-\ i\ v\ k\ a_1\ \cdots\ a_k$：删除边 $(a_1,v),\cdots,(a_k,v)$

  加边之前会保证原来没有这条边，删边之前会保证原来有这条边。
  每次操作后，可以得到一个连通性矩阵 $a$（$a_{i,j}=1$ 表示 $i$ 能到 $j$），输出

$$\bigg(\sum_{i,j=1}^n a_{i,j}A^{i-1}B^{j-1}\bigg)\ \text{mod}\ 2^{32}$$

  $1 \leq n \leq 400,\ 1 \leq q \leq 800,\ 1 \leq A,B \leq 10^9$
  3s

解法1

  每个点维护一个 bitset 表示它能到哪些点。
  每次操作时，暴力重构 $v$ 的 bitset，然后 bfs 一下把能到 $v$ 的点找出来，按拓扑序更新它们的 bitset。维护 bitset 时顺便维护答案。
  对于加边操作的更新，是 $bitset_i = bitset_i \vee bitset_v$。这个的时间主要在于图的遍历，边表是 $O(n^2)$ 的，因此时间是 $O\big(q(n^2+n\frac n{64})\big)=O(qn^2)$。
  对于删边操作的更新，是 $bitset_i = \bigvee_{x \in \text{out}(i)}bitset_x$（$\text{out}(i)$ 表示 $i$ 的出点），由于之前是或操作不可撤销，因此这个要对于 $i$ 枚举它的出点重新算，因此是 $O\big(q(n^2+n^2\frac n{64})\big)=O(\frac{qn^3}{64})$。

  因此总的时间是 $O(\frac{qn^3}{64})$，算出来 8 亿但是跑过去了。

解法2

  上面的解法，加边很优秀，但是删边不太行，这是因为删边的时候由于维护的是“是否连通”，所以无法快速撤销一个出点的影响。

  那什么可以撤销呢？方案数就可以撤销！

  记 $f_{i,j}$ 表示 $i$ 走到 $j$ 的方案数，给它模个 $10^9+7$ 啥的（不放心就多模几个）。
  每次操作时，暴力重算 $f_{v,\cdot}$ 或者 $f_{\cdot,v}$，然后对于所有 $(i,j)$，先 $f_{i,j}-=$原来的$f_{i,v}+f_{v,j}$，再 $+=$新的$f_{i,v}+f_{v,j}$。

  这样就是 $O(qn^2)$ 的了。

代码

// 解法1

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef unsigned int uint;

const int maxn=405;

int n,q,len,x[maxn];
uint A[maxn],B[maxn];
bool mp[maxn][maxn];
bitset<maxn> a[maxn];

void ReadChar(char &ch)
{
	ch=getchar();
	while (ch!='+' && ch!='-' && ch!='o' && ch!='i') ch=getchar();
}

bool bz[maxn];
void dfs1(int k,int v)
{
	if (v!=k) a[v][k]=1;
	bz[k]=1;
	fo(i,1,n) if (mp[k][i] && !bz[i]) dfs1(i,v);
}

int d[3*maxn],dg[maxn];
void topo(int v,char ty)
{
	fo(i,1,n) bz[i]=0, dg[i]=0;
	int j=0;
	if (ty=='o') d[j=1]=v;
		else fo(i,1,len) d[++j]=x[i];
	for(int i=1; i<=j; i++)
	{
		fo(go,1,n) if (mp[go][d[i]])
		{
			dg[go]++;
			if (!bz[go]) bz[ d[++j]=go ]=1;
		}
	}
}

uint ans,Ans[maxn];
void Redo(int v)
{
	ans-=Ans[v];
	Ans[v]=0;
	fo(i,1,n) if (a[v][i]) Ans[v]+=A[v-1]*B[i-1];
	ans+=Ans[v];
}

int main()
{
	freopen("reachability.in","r",stdin);
	freopen("reachability.out","w",stdout);
	
	scanf("%d %d %u %u",&n,&q,&A[1],&B[1]);
	A[0]=B[0]=1;
	fo(i,2,n) A[i]=A[i-1]*A[1], B[i]=B[i-1]*B[1];
	while (q--)
	{
		char ch1,ch2; int v;
		ReadChar(ch1), ReadChar(ch2);
		scanf("%d %d",&v,&len);
		fo(i,1,len)
		{
			scanf("%d",&x[i]);
			if (ch2=='o') mp[v][x[i]]^=1; else mp[x[i]][v]^=1;
		}
		
		if (ch2=='o')
		{
			a[v].reset();
			fo(i,1,n) bz[i]=0;
			dfs1(v,v);
			Redo(v);
		}
		
		topo(v,ch2);
		if (ch1=='+')
		{
			int j=0;
			if (ch2=='o') d[j=1]=v;
				else fo(i,1,len) d[++j]=x[i];
			for(int i=1; i<=j; i++)
			{
				a[d[i]]|=a[v];
				if (d[i]!=v) a[d[i]][v]=1;
				Redo(d[i]);
				fo(go,1,n) if (mp[go][d[i]])
				{
					if (--dg[go]==0) d[++j]=go;
				}
			}
		} else
		{
			int j=0;
			if (ch2=='o') d[j=1]=v;
				else fo(i,1,len) d[++j]=x[i];
			for(int i=1; i<=j; i++)
			{
				a[d[i]].reset();
				fo(go,1,n) if (mp[d[i]][go]) a[d[i]]|=a[go], a[d[i]][go]=1;
				Redo(d[i]);
				fo(go,1,n) if (mp[go][d[i]])
				{
					if (--dg[go]==0) d[++j]=go;
				}
			}
		}
		
		printf("%u\n",ans);
	}
}