Solution

主播从开这道题到 AC 用了整整一个小时。文末会分析我是如何被卡住。

看到题，哇是我不擅长的博弈。那看一眼部分分。

前两个 Sub：图是一个 DAG，所以可以 DP。

Sub 3 可能不是很好做，看一眼 Sub 4。

注意到，答案肯定是 $1$ 或者 $2$。显然如果 $a_1 = 2$ 那么返回 $2$。

否则，先手一定会将棋子移动到另一个 $2$ 上，除非不能操作；后手会接着将棋子移动到另一个 $1$ 上，除非不能操作。

因此棋子只会在 $a_x \neq a_y$ 的边上移动。建立出这样的图。

我们可以将博弈改为：在一个有向图上有一个棋子。每个人可以把棋子沿着有向边移动一步。先手获胜，当且仅当后手某一步不能移动。其他情况下都是后手获胜。问最后谁胜。

如果所有点都有出度，那么显然后手获胜，因为先手无论如何都不能是后手卡死。

否则，找到一个出度为 $0$ 的点。在这个点上，先手必败。而找到所有能到达它的点，它们都是先手必胜的（因为能转移到先手必败态）。

显然我们不会向先手必败态转移，所以我们可以把这一轮确定胜负状态的点全部删掉。然后继续重复找 $0$ 出度点的过程。

使用类似拓扑排序的手段维护，即可做到 $O(n+m)$。

回到原题，发现我们很容易判断答案是否 $\ge$ 某个给定的值。

主播计数题做魔怔了，想用 $\sum_{i \ge 1} [ans \ge i]$ 来计算答案。想了一万年都不知道怎么维护。

后来发现直接二分答案即可，复杂度 $O((n+m) \log V)$，足以通过本题。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=250000+10,MAXM=500000+10;
int n,m,b[MAXN],a[MAXN],deg[MAXN],del[MAXN],sg[MAXN],u[MAXM],v[MAXM];
vector<int> G[MAXN],g[MAXN];
int check(int lim) {
	ffor(i,1,n) a[i]=(b[i]>=lim)+1,G[i].clear(),g[i].clear();
	ffor(i,1,m) {
		int x=u[i],y=v[i];
		if(a[x]!=a[y]) G[x].push_back(y),g[y].push_back(x);	
	}
	if(a[1]==2) return 1;
	memset(sg,-1,sizeof(sg));
	queue<int> q;
	ffor(i,1,n) deg[i]=G[i].size();
	ffor(i,1,n) if(G[i].size()==0) q.push(i);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		sg[u]=0;
		for(auto v:g[u]) if(sg[v]==-1) {
			sg[v]=1;
			for(auto w:g[v]) {
				--deg[w];
				if(!deg[w]&&sg[w]==-1) {
					sg[w]=0,q.push(w);
				}
			}
		}
	}
	if(sg[1]==1) return 1;
	return 0;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,n) cin>>b[i];
	ffor(i,1,m) cin>>u[i]>>v[i];
	int ans=0,l=0,r=1000000000;
	while(l<=r) {
		int mid=(l+r>>1);
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;	
	}
	cout<<ans;
	return 0;
}