C. Canvas Painting
贪心。
初始时画布上有 \(n\) 种颜色。每次操作最多可以减少一种颜色（通过改变一个位置的颜色，使其与另一个位置的颜色相同）。因此，问题转化为如何最大化有效操作次数（即减少颜色的次数），最终答案即为 \(n\) 减去有效操作次数。
将操作区间按左端点分组并排序。使用一个小顶堆维护当前可用的操作区间的右端点。
从左到右处理每个关键左端点之间的区间段，对于每个位置，检查是否有可用的操作，即左端点不超过当前位置且右端点不小于当前位置的操作。优先使用右端点最小的操作来覆盖当前位置，因为右端点小的操作适用范围有限，优先使用可避免浪费。
每成功使用一个操作，有效操作次数加一。
最终答案即为 \(n\) 减去有效操作次数。
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int m, n;cin >> m >> n;map<int,vector<int>> mp;for (int i = 0; i < m; i += 1) {int l, r;cin >> l >> r;mp[l].push_back(r);}int ans = n;vector adj(mp.begin(), mp.end());priority_queue<int,vector<int>,greater<>> Q;for (int i = 0; i < (int)adj.size(); i += 1) {auto &[l ,ve] = adj[i];for (auto &r : ve) {Q.push(r);}int next = i + 1 == (int)adj.size() ? n : adj[i + 1].first;for (int j = l; j < next; j += 1) {while (!Q.empty() && Q.top() <= j) {Q.pop();}if (Q.empty()) {break;}ans -= 1;Q.pop();}}cout << ans << "\n";}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}
D. Min-Max Tree
树形DP。
题意可以看成将树拆成若干条链，然后选哪些链即可，记链的两端为最大最小值，则链的方向为最大值到最小值的方向。
设 \(dp_{x,0/1/2}\) 表示 \(x\) 作为中间点，作为最大值向下传递，作为最小值向上传递。
\(x\) 作为中间点时，如果向上/向下的贡献为 \(0\) 时，此时也作为最小/最大值。
则有转移方程：
\[Sum = \sum_{v\in Sub_u}dp_{v,0}
\]
\[up = \max(Sum,\max_{v\in Sub_u} (Sum-dp_{v,0}+dp_{v,1}+a_u-a_v))
\]
\[down = \max(Sum,\max_{v\in Sub_u}(Sum - dp_{v,0}+dp_{v,2}+a_v-a_u))
\]
\[dp_{x,0} = up + down - Sum,\ dp_{x,1}=down,\ dp_{x, 2} = up
\]
#include <bits/stdc++.h>using namespace std;using i64 = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i += 1) {cin >> a[i];}vector e(n + 1, vector<int>());for (int i = 1; i < n; i += 1) {int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}vector dp(n + 1,array<i64,3>());auto dfs = [&](auto &&self, int u, int fa)->void{i64 sum = 0;for (auto &v : e[u]) {if (v == fa) {continue;}self(self, v, u);sum += dp[v][0];}i64 up = sum, down = sum;for(auto &v : e[u]){if(v == fa) continue;up = max(up, sum - dp[v][0] + dp[v][2] + a[v] - a[u]);down = max(down, sum - dp[v][0] + dp[v][1] + a[u] - a[v]);}dp[u] = {up + down - sum, down, up};};dfs(dfs, 1, 0);cout << dp[1][0] << "\n";return 0;
}