[CSP-S 2022] 星战
这么长时间过去都快不会写题解了。
嗯……不过还是稍微记一下会比较好。
题意看完之后就是让我们去判断整张图是否是一个内向基环树森林。
然后这个事情判度数肯定是好的，每个点的出度都为 \(1\) 即可。
但是这个维护很奇葩，想不出来什么维护方法。
然后被 Sum Hash 震撼到了。
干脆想办法看看是不是每个点都出现了一次。
简单来说，首先给每个点一个随机的 Hash 值 \(h (x)\)。
然后，定义每个点的一个值 \(f(x)\)，令 \(f(x) = \sum _ {(y,x) \in E}h (y)\)。
因为题目的修改操作挺特殊的（只针对出点是该点的边），因此每个 \(f(x)\) 和 \(\sum f(x)\) 都是可以在 \(O ( 1 )\) 的复杂度下维护的。
那么维护这个 \(\sum f(x)\) 的作用在什么地方？
如果我们想一想，当 \(\sum h(x) = \sum f(x)\) 的时候，最有可能的情况是什么？
凭直觉得到，最有可能是所有点出度为 \(1\) 的时候。
Hash 其实就是这么个很不讲道理的东西，很多时候就是直觉上正确就能用 Hash……
我们维护 \(f(x)\) 即可。
当然，为了减小出错的可能性，多做几组 Hash 是更好的。这里我就做了 \(32\) 组，但是准确性足够了。
另外喷一下这个官方造数据的（全输出否都能得 45pts……）。
总的时间复杂度是 \(O(n+m+kq)\) 的（其中 \(k\) 指 Hash 的组数）。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=5e5;
ll n,m,u,v,tot,q;
ll ver[N+5],nxt[N+5],head[N+5],a[35][N+5],f[35][N+5],bgn[35][N+5]
,ff[N+5],hsh[N+5];
inline void Add(ll u,ll v) {ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
int main() {
n=read();m=read();
for(ll i=1;i<=m;i++) {u=read();v=read();Add(u,v);}
srand(73939133);
for(ll k=0;k<=31;k++) {
for(ll i=1;i<=n;i++) {a[k][i]=rand();hsh[k]+=a[k][i];}
for(ll i=1;i<=n;i++) {
for(ll j=head[i];j;j=nxt[j]) {
bgn[k][ver[j]]+=a[k][i];f[k][ver[j]]+=a[k][i];
}
}
for(ll i=1;i<=n;i++) ff[k]+=f[k][i];
}
q=read();
while(q--) {
ll t=read();
if(t==1) {
u=read();v=read();
for(ll k=0;k<=31;k++) {f[k][v]-=a[k][u];ff[k]-=a[k][u];}
}
if(t==2) {
u=read();
for(ll k=0;k<=31;k++) {ff[k]-=f[k][u];f[k][u]=0;}
}
if(t==3) {
u=read();v=read();
for(ll k=0;k<=31;k++) {f[k][v]+=a[k][u];ff[k]+=a[k][u];}
}
if(t==4) {
u=read();
for(ll k=0;k<=31;k++) {ff[k]+=bgn[k][u]-f[k][u];f[k][u]=bgn[k][u];}
}
ll flg=0;
for(ll k=0;k<=31;k++) {
if(ff[k]!=hsh[k]) {flg=1;break;}
}
if(flg) printf("NO\n");
else printf("YES\n");
}
return 0;
}