$\tt Link$。

简要题意

有一个 $n$ 个点 $m$ 条有向边的图，每条边有可用和不可用两个状态。有 $q$ 个操作：

• 操作 $\tt1$：让一条可用的边变得不可用
• 操作 $\tt2$：让一个点的所有入边中，可用的变得不可用
• 操作 $\tt3$：让一条不可用边变得重新可用
• 操作 $\tt4$：让一个点的所有入边中，不可用的变得可用

每次操作之后，如果同时满足

• 条件 $\tt1$：从每个点开始都可以无限的沿着可用边（有向）走下去。
• 条件 $\tt2$：每个点只有一条出边可用

就输出 YES，否则输出 NO。

60 分的部分分

暴力太简单不讲。

首先我们分析条件 $\tt2$，发现这应该是一棵内向基环树。

而内向基环树是一个环上挂着若干棵儿子向父亲连有向边的树，每个点可以先沿着有向边走上环，然后在环上无限走。所以必然满足条件 $\tt1$。

那么最后只需要判断条件 $\tt2$ 即可。

我们维护一个出度数组。发现操作 $\tt1$ 和 $\tt3$ 对出度数组的改变都是 $O(1)$ 的。于是暴力模拟出度数组的变化并动态维护出度为 $1$ 的点的个数，拿到 $\tt50pts$。

然后发现如果只有操作 $\tt2$，$q$ 次操作一共只会最多删掉 $O(m)$ 条边，对出度数组产生最多 $O(m)$ 的改变。所以同上，结合均摊分析，拿到 $\tt60pts$。

虽然笔者的思考止步于此，但是我拿的分可不止 $\tt60pts$。

于是靠着官方数据用脚造以及官方少爷机的神速，$\tt85pts$ 翻身了。

评测链接。

正解

对条件 $\texttt{1,2}$ 的分析还是同上。但 $\texttt{2,4}$ 操作并不是暴力模拟。

我们对每个点定义一个权值，它是一个随机数。

然后对于每一个点 $v$，记录 $a_v=\sum w_u[\text{exist }\texttt{edge}\{u\to v\}]$。

然后操作 $\texttt{1,3}$ 就让 $a_v$ 减去或加上 $w_u$。

操作 $\texttt{2,4}$ 记录原来的 $a$ 数组 $a^\prime$，然后让 $a_u\gets0$ 或者 $a_u\gets a^\prime_u$。

在更改的过程中动态维护 $\sum a_u$ 的值。

如果 $\sum a_u=\sum w_u$，那么每个点只有一个出边。

总结

用到了哈希的思想，正解写起来比 $\tt60pts$ 代码还短。

哈希思维难度大于部分分？但是想下来其实挺简单的。果然自己的思维还是有不足之处。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n,m,q,a[N];
long long to[N],sum[N],tot,ans;

int main(){
	mt19937 rnd(time(0));
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i) ans += (a[i] = rnd());
	for(int i = 1,u,v;i <= m;++i)
		scanf("%d%d",&u,&v),to[v] += a[u],sum[v] = to[v],tot += a[u];
	scanf("%d",&q);
	for(int i = 1,t,u,v;i <= q;++i){
		scanf("%d%d",&t,&u);
		if(t == 1) scanf("%d",&v),to[v] -= a[u],tot -= a[u];
		if(t == 2) tot -= to[u],to[u] = 0;
		if(t == 3) scanf("%d",&v),to[v] += a[u],tot += a[u];
		if(t == 4) tot += sum[u] - to[u],to[u] = sum[u];
		puts(tot == ans ? "YES" : "NO");
	}
	return 0;
}

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e5 + 10;
LL r[N], w[N], g[N];
int main()
{
    freopen("a.in", "r", stdin);
    mt19937 myrand(time(0));
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)w[i] = myrand();
    LL sum = 0;
    for (int i = 1; i <= n; i++)sum += w[i];
    memset(r, 0, sizeof(r));
    memset(g, 0, sizeof(g));
    LL now = 0;
    for (int i = 1, x, y; i <= m; i++)
    {
        scanf("%d%d", &x, &y);
        r[y] += w[x];
        g[y] = r[y];
        now += w[x];
    }
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int op, x, y;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%d", &x, &y);
            r[y] -= w[x];
            now -= w[x];
        }
        else if (op == 2)
        {
            scanf("%d", &x);
            now -= r[x];
            r[x] = 0;
        }
        else if (op == 3)
        {
            scanf("%d%d", &x, &y);
            r[y] += w[x];
            now += w[x];
        }
        else
        {
            scanf("%d", &x);
            now += g[x] - r[x];
            r[x] = g[x];
        }
        puts(now == sum ? "YES" : "NO");
    }
    return 0;
}

“我们能不能进行一次反攻？”
“不可以，总司令。”
“我们可不可以AC这题？”
“不可以，总司令。”
“你能不能不回答‘不可以’？”
“不可以，总司令。”
“为什么？”
“因为我回答‘不可以’有足足45%的正确率。”

45分代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1,x;i<=m;i++)scanf("%d%d",&x,&x);
	int q;scanf("%d",&q);
	while(q--)puts("NO");
}