A. Extreme Subtraction
把这个数组差分一下，发现操作一的作用是把 (d_1) 的大小分给 (d_i)，而操作二的作用是把 (d_i) 减去任意值，目标是把 (d) 的值都变为 (0)。对于 (d) 中大于 (0) 的值，就直接用操作二就行了；对于小于 (0) 的值，那它只能用 (d_1) 补偿；所以就比较一下 (b_1) 和 (- sumlimits_{i=2}^n[b_i<0] imes b_i)的大小就行了。
B. Identify the Operations
遍历 (b)，找到 (b_i) 在 (a) 中的位置，那么只能删除它左边的那个或右边的那个；但假如左边那个是将来的 (b) 的话，那就不能删了；同时会发现，删左边和删右边对序列的影响都是一样的，都是从两个能删的数变成两个能删的数。那就很简单了。
fin >> n >> m;
int mn = 1e9 + 1e2, mx = -1e9 - 1e2, ans = 1;
for (int i = 1; i <= n; i++) fin >> a[i];
for (int i = 1; i <= m; i++) fin >> b[i];
for (int i = 1; i <= n; i++) pnt[a[i]] = i;
for (int i = 1; i <= n; i++) vis[i] = 0;
for (int i = 1; i <= m; i++) vis[pnt[b[i]]] = true;
vis[0] = vis[n + 1] = true;
for (int i = 1; i <= m; i++)
{
(ans *= 2 - vis[pnt[b[i]] - 1] - vis[pnt[b[i]] + 1]) %= mod;
vis[pnt[b[i]]] = false;
}
fout << ans << Endl;
C. Graph Transpositions
惯例分层图。但是分层图的深度特别大怎么办？我们发现，(2^{18}) 次方就已经大于 (n) 了，所以暂且只建这么 (18) 层。
如果这 (18) 能到，那就 OK 了。如果不能，那就有讲究了。我们发现这时我们的第一追求是层数少，然后才是这层内的距离近。所以我们可以一层一层拓展，就可以保证层数少。
这么做还是 (O(n^2))的，还需要加上一个剪枝——若当前点在以前的层中已经访问，那就不用再走它，于是复杂度就对了。还有就是 (18) 层以后的图上，存的 (dis) 就不用包括 (2^k) 次方了，就可以处理需要取模的最小值了。
D. Sum
神奇结论题：最多只有一列选了一部分，其他列要么全选要么不选。证明使用反证法就行了。这样问题就从多重背包变成了扣点一个点的 0/1 背包。这个问题可以使用分治或分块处理。
inline update(vector<u64>& f, int sze, u64 val) {
for (int i = k - sze; i >= 0; i--) {
f[i + sze] = max_(f[i + sze], f[i] + val);
}
}
u64 ans;
void solve(int l, int r, vector<u64> f)
{
if (l == r) {
for (int i = 0; i <= min_(k, m[l]); i++) {
ans = max_(ans, f[k - i] + a[l][i]);
}
return;
}
int mid = (l + r) >> 1; vector<u64> fl = f, fr = f;
for (int i = l; i <= mid; i++) update(fr, m[i], a[i][m[i]]);
for (int i = r; i > mid; i--) update(fl, m[i], a[i][m[i]]);
solve(l, mid, fl); solve(mid + 1, r, fr);
}