P9870 [NOIP2023] 双序列拓展 题解

NOIP2023 T3，特殊性质题。

什么是特殊性质题？就是题目给出了你极其神秘的性质，从而引导你想出正解。

本篇题解将从部分分的角度，一步步讲述部分分与正解的关系。这样看的话，本题会变得十分简单。

\(\text{Task } 1∼7, O(Tnm)\)

简化题意其实就是要求满足最终序列里的 \((f_i-g_i)\) 同号。那么我们只考虑 \(f_i<g_i\) 的情形，另一种是等价的。

看上去 \(l_0\) 很大，但其实只需要计算出 \(X,Y\) 的 \(L\) 序列一一匹配即可。记匹配序列分别为 \(x,y\)。

那么对于 \(O(nm)\) 的 dp，套路地设 \(dp_{i,j}\) 表示 \(x\) 匹配到 \(i\)，\(y\) 匹配到 \(j\) 的合法性。从 \((i,j)\) 转移到 \((i,j+1)\)，\((i+1,j)\) 是容易的。

代码：

int DP() {
	if (x[1] == y[1]) return 0;
	int fg = 0;
	if (y[1] > x[1]) fg = 1;
	memset(dp, 0, sizeof dp);
	dp[1][1] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (dp[i][j]) {
				if (fg == 0 && x[i + 1] > y[j]) dp[i + 1][j] = 1;
				if (fg == 1 && y[j] > x[i + 1]) dp[i + 1][j] = 1;
				if (fg == 0 && x[i] > y[j + 1]) dp[i][j + 1] = 1;
				if (fg == 1 && y[j + 1] > x[i]) dp[i][j + 1] = 1;
			}
	return dp[n][m];
}

\(\text{Task } 8∼14, O(T(n+m))\) 特殊性质

dp 的状态是难以优化的，考虑特殊性质是什么意思。

\(x\) 的最小值在序列的最后端，说明这个做法大概和维护一些最小值相关联。又因为这是一个线性的复杂度，使我们想到贪心处理。这样的通常套路是枚举一个变量，同时双指针统计第二个变量去做。

simple 的想法是枚举 \(1\sim m\) 的 \(y\)，对于每一个 \(y\) 拓展 \(x\)，直到不能拓展为止。并检查合法性。

但这样显然没有正确性，原因是当前 \(y\) “占了过多” 的 \(x\)，导致没有足够的合法 \(x\) 和之后的 \(y\) 匹配。

如何解决这个问题？要让更多的 \(y\) 得到匹配，就是不让当前的 \(y\) 去挤占可以去做贡献的更小的 \(x\)，也就是 让每个最小的 \(x\) 去拓展更多的 \(y\)。 我们转而枚举 \(x\)，对于每个 前缀最小值 \(x_i\)，我们可以让它尽情放飞地去匹配尽量多的 \(y\)，假设匹配到了 \(y_i\)，下一个前缀最小值是 \(x_j\)，那么 \([x_i,x_{j-1}]\) 直接匹配 \([y_1,y_i]\) 中的最大值 \(y_{\max}\) 是最优的，至于 \(y_{\max}\) 之后的部分，由于是 \(x_i\) 拓展到的，还有 \(x_j\) 等着匹配这些个拓展出的部分，且让 \(x_j\) 去拓展新的序列也一定更优。这样一来事实上形成了一些个区间。由于 \(y\) 的最大值同样在序列末尾，并不存在 \(x\) 到终点之后没有 \(y\) 与之匹配的情形。那么对于不是前缀最小值的 \(x\)，检查它和 \(y_{\max}\) 的大小关系即可。这样做正确的核心是在恰当的时机让当前匹配的 \(y\) "放手"，避免 "侵占资源"，让那个 \(x\) 来拓展更多的 \(y\)。

代码：

int chk() {
	for (int i = 1; i <= n; i++)
		mx[i] = max(mx[i - 1], y[i]);
	int j = 0, mn = 1e9;
	for (int i = 1; i <= n; i++) {
		if (x[i] < mn) {
			while (j < m && x[i] < y[j + 1])
				++j;
		}
		else if(x[i] >= mx[j]) return 0;
		mn = min(mn, x[i]);
	}
	return j == m;
}

\(\text{Task } 15\sim 20, O(T(n+m))\) 正解

特殊性质的提示还 TM 不够明显吗？？

将 \(x,y\) 序列分别按照最大，最小值分成两段处理即可。

完整代码：

#include <bits/stdc++.h>
#define N 500005
#define int long long
using namespace std;
int c, n, m, q;
int x[N], y[N], xx[N], yy[N];
int mx[N];
int nx[N], ny[N];
int chk(int p, int q) {
	if (nx[1] >= ny[1]) return 0;
	mx[0] = -1e9;
	for (int i = 1; i <= q; i++)
		mx[i] = max(mx[i - 1], ny[i]);
	int j = 0, mn = 1e9;
	for (int i = 1; i <= p; i++) {
		if (nx[i] < mn) {
			while (j < q && nx[i] < ny[j + 1])
				++j;
		}
		else if(nx[i] >= mx[j]) return 0;
		mn = min(mn, nx[i]);
	}
	return j == q;
}
int kudo() {
	if (x[1] == y[1]) return 0;
	if (x[1] > y[1]) {
		swap(x, y);
		swap(n, m);
	}
	int mn = 1e9, p = 0;
	for (int i = 1; i <= n; i++)
		mn = min(mn, x[i]);
	for (int i = 1; i <= n; i++)
		if (mn == x[i]) {
			p = i;
			break;
		}
	int mx = -1e9, q = 0;
	for (int i = 1; i <= m; i++)
		mx = max(mx, y[i]);
	for (int i = 1; i <= m; i++)
		if (mx == y[i]) {
			q = i;
			break;
		}
	int cp = 0, cq = 0;
	for (int i = 1; i <= p; i++)
		nx[++cp] = x[i];
	for (int i = 1; i <= q; i++)
		ny[++cq] = y[i];
	int ans = chk(cp, cq);
	cp = 0, cq = 0;
	for (int i = n; i >= p; i--)
		nx[++cp] = x[i];
	for (int i = m; i >= q; i--)
		ny[++cq] = y[i];
	ans &= chk(cp, cq);	
	return ans;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> c >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		cin >> x[i], xx[i] = x[i];
	for (int i = 1; i <= m; i++)
		cin >> y[i], yy[i] = y[i];
	int nn = n, mm = m;
		cout << kudo();
		for (int w = 1; w <= q; w++) {
			int nx, ny;
			cin >> nx >> ny;
			while (nx--) {
				int p, t;
				cin >> p >> t;
				x[p] = t;
			}
			while (ny--) {
				int p, t;
				cin >> p >> t;
				y[p] = t;
			}
			cout << kudo();
			n = nn, m = mm;
			for (int i = 1; i <= n; i++)
				x[i] = xx[i];
			for (int i = 1; i <= m; i++)
				y[i] = yy[i];
		}
	return 0;
}