CF1710E Two Arrays

\(\text{Solution}\)

一道有难度的博弈论，对于一个点最多走\(1000\)次其实是没有意义的，可以看成只走\(1\)次。考虑去二分答案\(mid\)，那么对于原图就会变成很多个黑白点，那么每一次操作就必须要从一个颜色的点跳到另一颜色的点，不然对手就会直接结束游戏，这不是经典的二分图博弈吗?用一下结论，所以起点一定要在所有最大匹配中\(Alice\)才会赢，但我们很难去求最大匹配。
考虑去求最大独立集，发现\(a, b\)值的顺序是与我们的答案无关的，对\(a, b\)排序，那么原图就会变为\(0\)在一边，\(1\)在一边，对于选中的一个坐标\(x, y\)，只需求\(\le x, \le y\)中有几个\(0\)，\(>x,>y\)中有几个\(1\)即可，发现\(y\)是随\(x\)的增大而增大的，双指针即可。

\(\text{code}\)

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 2e5 + 5; 
int n, m, X, Y, ln[N], lm[N];

struct nd{int z, id;}a[N], b[N];
bool cmp(nd x, nd y){return x.z < y.z;}
int check(int lit) {
	if (a[X].z + b[Y].z <= lit) return 1;
	LL res = 0, tmp = 0, sum = 0;
	for (int x = m, y = 1; y <= n; y++) {
		while (x && a[y].z + b[x].z > lit) x--;
		ln[y] = x;
	}
	for (int x = n, y = 1; y <= m; y++) {
		while (x && a[x].z + b[y].z > lit) x--;
		lm[y] = x, sum += (LL)n - x;
	}
	tmp = sum, res = sum - 1LL;
	for (int y = 0, x = 1; x <= n; x++) {
		sum -= min(m - ln[x], m - y) - min(ln[x], y);
		while (y < m && sum - (min(n - lm[y + 1], n - x) - min(lm[y + 1], x)) >= sum)
			y++, sum -= min(n - lm[y], n - x) - min(lm[y], x);
		tmp = max(tmp, sum); 
	}
	sum = -1;
	for (int i = 1; i <= n; i++) sum += m - ln[i];
	for (int x = 1, y = 0; x <= n; x++) {
		sum -= (x == X ? min(m - ln[x] - 1, y < Y ? m - y - 1 : m - y) : min(m - ln[x], m - y)) - min(ln[x], y);
		while (y < m && sum - (y + 1 == Y ? min(n - lm[y + 1] - 1, x < X ? n - x - 1 : n - x) : min(n - lm[y + 1], n - x)) + min(lm[y + 1], x) >= sum)
			y++, sum -= (y == Y ? min(n - lm[y] - 1, x < X ? n - x - 1 : n - x) : min(n - lm[y], n - x)) - min(lm[y], x);
		res = max(res, sum); 
	}
	return (res + 1LL) != tmp;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++) scanf("%d",&a[i].z), a[i].id = i;
	for (int i = 1; i <= m; i++) scanf("%d",&b[i].z), b[i].id = i;
	sort(a + 1, a + 1 + n, cmp), sort(b + 1, b + 1 + m, cmp);
	for (int i = 1; i <= n; i++) X = (a[i].id == 1 ? i : X);
	for (int i = 1; i <= m; i++) Y = (b[i].id == 1 ? i : Y);
	int l = 1, r = (int)1e9, ans = 1;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", ans);
}