题目链接：https://codeforces.com/contest/1687/problem/C
题意简述
有两个长为 \(n\) 的数列 \(a\) 和 \(b\)。有 \(m\) 条线段，你可以进行任意次以下操作：
- 选择一条线段 \([l, r]\)，若 \(\sum\limits_{i = l}^r a_i = \sum\limits_{i = l}^r b_i\)，将 \(a\) 的 \([l, r]\) 段置为 \(b\)。
问是否能使 \(a\) 与 \(b\) 相同。
题解
这题其实非常简单。首先要转化问题。令两数组差的前缀和 \(s_n = \sum\limits_{i=1}^n (a_i - b_i)\)，则操作等价于：
- 若 \(s_{l-1} = s_r\)，将 \(s\) 的 \([l-1,r]\) 段置为 \(s_r\)。
问题等价于能否使 \(s\) 变为全 \(0\)。
这时问题已经很清晰了，我们倒序考虑操作，不难得到如下结论：
-
一次 \(s_{l-1} = s_r \ne 0\) 的操作是毫无意义的，也就是操作总有 \(s_{l-1} = s_r = 0\)。
-
那么，既然所有操作都要端点为 \(0\) 时才能操作，且最终的目标也是全 \(0\)，只要一次操作可以进行，立即进行总是最优的。且已经执行该操作后，不会需要再次执行。
考虑如何模拟这个过程。我们很容易想到类似拓扑排序的模型，将每条线段置为 \(0\) 时，对每个被置为 \(0\) 的点，判断其出边对应的操作是否可以执行了即可。进行所有操作后，判断 \(s\) 数组是否已经为全 \(0\) 即可。
每个点只会被置零一次。可以使用 set 维护尚未被置零的点，或者使用并查集甚至链表等其他手段保证正确复杂度。时间复杂度 \(O(n \log n)\) 或 \(O(n\alpha(n))\) 或 \(O(n)\)。
代码实现
我练习写了一版并查集，但再想想用 set 会方便简洁许多，因此在这里附上更短的代码。
#define int i64
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
vector<int> s(n + 1);
for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + a[i] - b[i]; }
vector<pair<int, int>> op;
queue<int> q;
vector<vector<int>> adj(n + 1);
set<int> nz;
for (int i = 1; i <= n; i++) {
if (s[i]) nz.insert(i);
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
l--;
op.push_back({l, r});
if (!s[l] && !s[r]) { q.push(i); }
if (s[l]) adj[l].push_back(i);
if (s[r]) adj[r].push_back(i);
}
while (q.size()) {
int id = q.front();
q.pop();
auto [l, r] = op[id];
for (auto it = nz.lower_bound(l); it != nz.end() && *it <= r;
it = nz.erase(it)) {
int x = *it;
s[x] = 0;
for (int u : adj[x]) {
auto [l, r] = op[u];
if (!s[l] && !s[r]) q.push(u);
}
}
}
if (ranges::count(s, 0) != (i64)s.size()) cout << "No\n";
else cout << "Yes\n";
}
#undef int