我承认开训前确实摆了太久，第一场训练赛根本没有进入状态。那么就从今天开始抑制惰性，好好训练吧！
L
题目大意：
给定 \(n\) 个正整数 \(a_i\) 和 \(q\) 次询问。每次询问给定 \(i\), \(j\)，修改：\(a_i\leftarrow a_i + j\)，（修改在后续询问中也生效）然后你需要统计此时有多少 \(a_i\) 满足：大于 \(a_i\) 的数的数目不小于 $\left \lfloor \frac n 2 \right \rfloor $。
难度： ~2000
知识点： 权值线段树 / 平衡树
为了方便叙述，我们重新定义中位数为升序排序后的 \(a_{\left \lceil \frac n 2 \right \rceil }\)。（也就是说在 \(n\) 为偶数时不取均值）
容易发现，小于中位数的元素一定符合统计要求，大于中位数的元素一定不符合统计要求。等于中位数的元素满足以下要求时符合：升序排序后， \(a_{\left \lceil \frac n 2 \right \rceil } \ne a_{ \left \lceil \frac n 2 \right \rceil + 1}\) 。
因此我们只需寻找一种数据结构支持以下操作：单点修改、查询给定下标的元素、查询小于某数的元素个数。各种数据结构都可以，这里就写一个权值线段树吧。
先离线对所有可能出现的数进行离散化，作为线段树的值域。线段树维护值域上各数的出现次数，各操作如下。
单点修改 ：原数出现次数--，新数出现次数++；
查询给定下标的元素 ：线段树上二分即可；
查询小于某数的元素个数 ：其实就是做区间查询；
好像确实什么难度。但为什么赛时没切？有点无语。
Code:
#include <bits/stdc++.h>
using namespace std;#define int long long
#define FOR(i,j,k) for (int i = j; i <= k; i++)
#define pb(x) push_back(x)const int N = 2e5 + 10;int T;
int n, Q;int a[N], b[N], q[N][2];
int t[N << 4];void build(int u, int l, int r) {if (l == r) {t[u] = 0; return;}int mid = (l + r) / 2;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);t[u] = t[u << 1] + t[u << 1 | 1];
}void modify(int u, int l, int r, int x, int d) {if (l == r) {t[u] += d; return;}int mid = (l + r) / 2;if (x <= mid) modify(u << 1, l, mid, x, d);else modify(u << 1 | 1, mid + 1, r, x, d);t[u] = t[u << 1] + t[u << 1 | 1];
}int qry(int u, int l, int r, int x) {if (l == r) return l;int mid = (l + r) / 2;if (x <= t[u << 1]) return qry(u << 1, l, mid, x);else return qry(u << 1 | 1, mid + 1, r, x - t[u << 1]);
}int ask(int u, int l, int r, int L, int R) {if (L > R) return 0;if (L <= l && r <= R) return t[u];int ret = 0, mid = (l + r) / 2;if (mid >= L) ret += ask(u << 1, l, mid, L, R);if (mid < R) ret += ask(u << 1 | 1, mid + 1, r, L, R);return ret;
}void solve() {cin >> n >> Q;vector<int> arr;unordered_map<int, bool> ump;unordered_map<int, int> id;FOR(i, 1, n) {cin >> a[i]; b[i] = a[i];if (ump[a[i]]) continue;ump[a[i]] = true;arr.pb(a[i]);}FOR(i, 1, Q) {cin >> q[i][0] >> q[i][1];b[q[i][0]] += q[i][1];if (ump[b[q[i][0]]]) continue;ump[b[q[i][0]]] = true;arr.pb(b[q[i][0]]);}int m = arr.size();sort (arr.begin(), arr.end());FOR(i, 0, m - 1) id[arr[i]] = i + 1;build(1, 1, m);FOR(i, 1, n) {modify(1, 1, m, id[a[i]], 1);}FOR(i, 1, Q) {modify(1, 1, m, id[a[q[i][0]]], -1);a[q[i][0]] += q[i][1];modify(1, 1, m, id[a[q[i][0]]], 1);int ans = 0;int k1 = qry(1, 1, m, (n + 1) / 2), k2 = qry(1, 1, m, (n + 1) / 2 + 1);if (k1 == k2) ans = ask(1, 1, m, 1, k1 - 1);else ans = ask(1, 1, m, 1, k1);cout << ans << '\n';}
}signed main() {cin >> T;while (T--) {solve();}return 0;
}
I
题目大意：
给定区间内 \(n - 1\) 个点的位置，每次操作选择一个不同点将其左右分割成两个区间。假设操作后两个新子区间的长度为 \(l_1, l_2\) ，则当次操作代价为 \(\min \left \{ l_1, l_2 \right \} \times \left \lceil \log_2 (l_1 + l _2) \right \rceil\)，不平衡度为 \(\left | l_1 - l_2 \right |\)。要求 \(n-1\) 次分割操作不平衡度单调不增，代价之和最小。
难度： ~2200
知识点： 区间DP，空间卡常
以为是小清新区间DP，但发现并非如此啊，原来是神人卡常题。
首先我们注意到子区间转移至父区间需要满足不平衡度的要求，所以我们设计的状态需要包含不平衡度的信息，方便转移。
此处我们设 \(dp_{l, r, m}\) 表示区间 \([l,r]\) ，若第一步割 \(m\) ，最终完全分割至少需要付出的代价。那么我们可以做出以下转移：
其中 \(w\) 表示该次转移产生的代价，也就是 \(\min \left \{ l_1, l_2 \right \} \times \left \lceil \log_2 (l_1 + l _2) \right \rceil\) ，\(l_1,l_2\) 可以通过预处理前缀和 \(\mathcal O(1)\) 求出。
同时 \(i\) 和 \(j\) 的取值有范围要求，必须在 \(dp_{l,m,i}\) 和 \(dp_{m+1,r,j}\) 的不平衡度小于等于父区间的范围内。此处若枚举 \(i,j\) 取值，时间复杂度 \(\mathcal O(n^4)\) ，无法通过本题。
考虑根据 \(dp_{l,r,m}\) 的不平衡度对 \(dp_{l,r}\) 序列进行排序，并做前缀最小值。由父状态得到不平衡度限制，便可在新的 \(dp_{l,r}\) 上进行二分，以得到最优转移。时间复杂度 \(\mathcal O(n^3\log n)\) ，可以通过此题。
但此题对空间的限制很严格。即使优化代码实现方法，只留两个 $420 \times 420 \times 420 $ 级别的 long long 数组依旧无法通过。必须再对空间常数做优化。
注意到 \(dp_{i,j,k}\) 只在 \(i \leq k < j\) 时有意义，也就是说当前的 \(dp\) 数组占据了大量的无效空间。
因此我们考虑对满足 \(i\leq k < j\) 的三元组 \((i, j, k)\) 按照字典序进行编号。这个编号可以以一个多项式的形式表示。通过演算可知，这样做可以将空间压缩至原来的六分之一。于是艰难通过本题。
Code:
#include <bits/stdc++.h>
using namespace std;#define int long long
#define FOR(i,j,k) for (int i = j; i <= k; i++)const int N = 422;
const int INF = 1e16;int T;
int n, cnt;
int a[N], sum[N], pre[N];struct sta {int imb, mn;bool operator < (const sta & x) & {return imb < x.imb;}
} g[(N - 1) * N * (N + 1) / 6];inline int calc(int i, int j, int k) {return pre[i - 1] + (j - i) * (j - i + 1) / 2 - (j - 1 - k);
}int Qry(int l, int r, int D) {if (l == r) return 0;int L = l, R = r - 1;int ans = INF;while (L <= R) {int mid = (L + R) / 2;if (g[calc(l, r, mid)].imb <= D) {L = mid + 1;ans = min(ans, g[calc(l, r, mid)].mn);} else {R = mid - 1;}}if (ans == INF) return -1;return ans;
}void solve() {cin >> n;FOR(i, 1, n) pre[i] = pre[i - 1] + (n - i + 1) * (n - i) / 2;FOR(i, 1, n) FOR(j, i + 1, n) FOR(k, i, j - 1) g[++cnt].mn = INF;FOR(i, 1, n) cin >> a[i], sum[i] = sum[i - 1] + a[i];FOR(i, 1, n - 1) {g[calc(i, i + 1, i)].mn = ceil(log2(a[i] + a[i + 1])) * min(a[i], a[i + 1]);;g[calc(i, i + 1, i)].imb = abs(a[i] - a[i + 1]);}if (n == 2) {cout << g[calc(1, 2, 1)].mn << '\n';return;}FOR(len, 3, n) {FOR(i, 1, n - len + 1) {int j = i + len - 1;FOR(m, i, j - 1) {int Lsz = sum[m] - sum[i - 1];int Rsz = sum[j] - sum[m];int D = abs(Lsz - Rsz);int ans1 = Qry(i, m, D), ans2 = Qry(m + 1, j, D);int pos = calc(i, j, m);if (ans1 == -1 || ans2 == -1) g[pos].mn = INF;else g[pos].mn = ans1 + ans2 + ceil(log2(Lsz + Rsz)) * min(Lsz, Rsz);g[pos].imb = D;if (len == n) {if (g[pos].mn == INF) cout << "-1 "; else cout << g[pos].mn << " ";}}int bg = calc(i, j, i), ed = calc(i, j, j - 1) + 1;sort(g + bg, g + ed);FOR(m, i + 1, j - 1) {g[calc(i, j, m)].mn = min(g[calc(i, j, m)].mn, g[calc(i, j, m - 1)].mn);}}}cout << '\n';
}signed main() {cin >> T;while (T--) solve();return 0;
}