杂题选记（10.26 - 11.1）

P12029 [USACO25OPEN] Election Queries G

记 \(c_i\) 为投票给 \(i\) 的人数。那么两头奶牛 \(x\)，\(y\) 能成为领队的条件是 \(c_x + c_y \ge c_max\)，其中 \(c_max = \max{c_i}\)。
考虑单次查询，用双指针可以轻松地做到 \(O(n)\)，二分带个 \(\log\) 也可以接受的。
卡在了一个重要结论，由于 \(\sum{c_i} = n\)，那么不同的 \(c_i\) 的取值最多有 \(O(\sqrt{n})\) 种（\(1 + 2 + \cdots + n = \frac{n(n + 1)}{2}\))。
那么我们开 \(N\) 个 \(set\) 记录 \(c_x = i\) 中最小/最大的 \(x\)，然后每次对还存在的 \(c_i\) 做一遍尺取就好了。
复杂度 \(O(Q{\log{N} + \sqrt{N}})\)。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
set<int> s, mn[N];
set<int, greater<int> > mx[N];
int c[N], a[N], n, q;
void upd(int x, int k){if(c[x]){mx[c[x]].erase(x), mn[c[x]].erase(x);if(mx[c[x]].empty()) s.erase(c[x]);}c[x] += k;if(c[x]){mx[c[x]].insert(x), mn[c[x]].insert(x);if(mx[c[x]].size() == 1) s.insert(c[x]);}
}
int qry(){auto l = s.begin(), r = s.end();int mny = 1e9, cmax = *s.rbegin(), ans = 0;
//	cout << cmax << '\n';while(l != s.end()){while(r != s.begin() && *prev(r) + *l >= cmax) --r, mny = min(mny, *mn[*r].begin());ans = max(ans, *mx[*l].begin() - mny);++l;}return ans;
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);cin >> n >> q;for(int i = 1; i <= n; ++i) cin >> a[i], c[a[i]]++;for(int i = 1; i <= n; ++i){if(c[i]) s.insert(c[i]), mx[c[i]].insert(i), mn[c[i]].insert(i);}while(q--){int x, k;cin >> x >> k;upd(a[x], -1);a[x] = k;upd(a[x], 1);cout << qry() << '\n';}return 0;
}

P12030 [USACO25OPEN] OohMoo Milk G

怎么说呢，感觉这题很玄乎。
可以发现，Fj 每天的操作就是对最大的 \(A\) 个数 + 1，然后 Nj 的操作就是对最大的 \(B\) 个数 - 1。
我们发现 Fj 每天加的那 \(A\) 个数总是固定的，就是原序列中最大的 \(A\) 个数。那么现在难点在于 Nj 的操作。
先考虑对前 \(A\) 大的数全部加 \(D\)。对于一些特别大的数，Nj 每次操作都会选择减他们，相当于这些数占用了一些固定的位置。但对于一些更小的数来说，我们要最小化 \(\sum x^{2}\)，根据凸性/均值，让他们更加平均是更优的。那么就类似云浅那场的 T2。我们考虑二分这个平均值 \(k\)，对于 \(a_i > k + D\) 的，这就是那些每次都必须减的数，会耗费 \(D\) 个操作次数。而对于其他的 \(a_i > k\)，我们会耗费 \(a_i - k\) 的操作次数把他们全部都调成这个平均值 \(k\)。由于题目限制总共操作次数不得超过 \(B \times D\)。我们找到最大的 \(k\) 使得操作次数刚好 \(\ge B \times D\)。假设 \(k\) 时耗费的次数是 \(check(k)\)，根据上面调整的过程，不难发现我们二分出的这个 \(k\)，它的 \(check(k) - B \times D < B\)。之所以会有这些超的，是因为整数均值就是一些是 \(k\)，一些是 \(k + 1\)。那么我们把多的那部分再调成 \(k + 1\) 即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, mod = 1e9 + 7;
int n, d, a, b, m[N];
int check(int k){int cnt = 0;for(int i = 1; i <= a; ++i){if(m[i] > k) cnt += min(d, m[i] - k);}return cnt;
}
signed main(){ cin.tie(nullptr)->sync_with_stdio(0);cin >> n >> d >> a >> b;for(int i = 1; i <= n; ++i) cin >> m[i];sort(m + 1, m + 1 + n, greater<int>());for(int i = 1; i <= a; ++i) m[i] += d;int l = 1, r = 2e9;while(l < r){int mid = (l + r + 1) >> 1;if(check(mid) < b * d) r = mid - 1;else l = mid;}int k = check(l) - b * d, ans = 0;for(int i = 1; i <= n; ++i){if(m[i] > l) m[i] -= min(d, m[i] - l);(ans += m[i] * m[i]) %= mod; }(ans += k * (2 * l + 1)) %= mod;cout << ans;return 0;
}

CF2150B Grid Counting

卡在了怎么处理 \(\max(x_i, y_i) = k\) 的条件上。事实上，可以把每个点的 \(\max(x_i, y_i)\) 画出来，发现是从左上角一圈一圈递增；同理，\(\max(x_i, n - y_i + 1)\) 是从右上角一圈一圈递增。稍微找一下规律，可以发现最终能涂色的那一部分是一个倒三角状物，那么再根据 \(a_i\) 的限制从下往上填算方案就好。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, mod = 998244353;
ll a[N], n, k, fac[N], ifac[N], inv[N];
ll C(int n, int m){if(m > n || n < 0) return 0;return fac[n] * ifac[m] % mod * ifac[n - m] % mod;}
void solve(){cin >> n;k = 0;for(int i = 1; i <= n; ++i) cin >> a[i], k += a[i];if(k != n || a[1] < 2) cout << 0 << '\n';else{ll ans = 1, cnt = 0;for(int i = (n + 1) / 2; i >= 1; --i){ans = (ans * C(n - 2 * (i - 1) - cnt, a[i])) % mod;cnt += a[i];}for(int i = (n + 1) / 2 + 1; i <= n; ++i){if(a[i] != 0){ ans = 0; break; }}cout << ans << '\n';}
}
int main(){cin.tie(nullptr)->sync_with_stdio(0);fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;for(int i = 2; i <= 2e5; ++i){fac[i] = (fac[i - 1] * i) % mod;inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;ifac[i] = (ifac[i - 1] * inv[i]) % mod;}int T; cin >> T;while(T--) solve();return 0;
}

CF2150C Limited Edition Shop

推等价条件：记 \(i\) 在 \(b_i\) 中出现的位置是 \(pos_i\)，那么 Alice 能从她喜爱的物品中选出一个子集 \(S\) 的条件是 \(\forall a_i \notin S, a_j \in S, i < j, pos_{a_i} < pos_{a_j}\)。
考虑 dp，\(f_{i, j}\) 表示 Alice 选到前 \(i\) 个物品，之前没选的物品中最大的 \(pos_{a_k}(k \le i) = j\) 的最大值。
有 \(\begin{cases} f_{i + 1, j} \gets f_{i, j} + v_{a_i + 1} & j < pos_{a_i + 1} \\ f_{i + 1, j} \gets \max_{k < j}{f_{i, k}} & j = pos_{a_i + 1} \\ f_{i + 1, j} \gets f_{i, j} & j > pos_{a_i + 1} \\ \end{cases}\)。
考虑线段树直接维护 \(f_j\)。从 \(i \to i + 1\) 时，发现 \(f_j\) 的转移是一段区间加，一次区间查最大值，和一次单点修改。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, inf = 1e18;
int n, v[N], a[N], b[N], pos[N], tag[N << 2], tr[N << 2];
#define ls(p) p << 1
#define rs(p) p << 1 | 1
void pushup(int p){ tr[p] = max(tr[ls(p)], tr[rs(p)]); }
void addtag(int p, int k){ tag[p] += k, tr[p] += k; }
void pushdown(int p){ if(tag[p]) addtag(ls(p), tag[p]), addtag(rs(p), tag[p]), tag[p] = 0; }
void add(int L, int R, int k, int p = 1, int pl = 0, int pr = n){if(L <= pl && R >= pr) return addtag(p, k);int mid = (pl + pr) >> 1;pushdown(p);if(L <= mid) add(L, R, k, ls(p), pl, mid);if(R > mid) add(L, R, k, rs(p), mid + 1, pr);pushup(p); 
}
void upd(int x, int k, int p = 1, int pl = 0, int pr = n){if(pl == pr) return tr[p] = k, void();int mid = (pl + pr) >> 1;pushdown(p);if(x <= mid) upd(x, k, ls(p), pl, mid);else upd(x, k, rs(p), mid + 1, pr);pushup(p);
}
int query(int L, int R, int p = 1, int pl = 0, int pr = n){if(L <= pl && R >= pr) return tr[p];int mid = (pl + pr) >> 1, ret = -inf;pushdown(p);if(L <= mid) ret = query(L, R, ls(p), pl, mid);if(R > mid) ret = max(ret, query(L, R, rs(p), mid + 1, pr));return ret; 
}
void clear(int p = 1, int pl = 0, int pr = n){tag[p] = tr[p] = 0;if(pl == pr) return;int mid = (pl + pr) >> 1;clear(ls(p), pl, mid), clear(rs(p), mid + 1, pr);
}
void solve(){cin >> n;clear();for(int i = 1; i <= n; ++i) cin >> v[i];for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= n; ++i) cin >> b[i], pos[b[i]] = i;upd(0, v[a[1]]);if(1 < pos[a[1]]) add(1, pos[a[1]] - 1, -inf);if(pos[a[1]] < n) add(pos[a[1]] + 1, n, -inf);for(int i = 2; i <= n; ++i){int mx = query(0, pos[a[i]]);add(0, pos[a[i]] - 1, v[a[i]]); // chosen upd(pos[a[i]], mx); // unchosen}cout << tr[1] << '\n'; 
}
signed main(){cin.tie(nullptr)->sync_with_stdio(0);int T; cin >> T;while(T--) solve();return 0;
}