题解 CF643G 【Choosing Ads】

> [CF643G Choosing Ads](https://codeforces.com/contest/643/problem/G) ## 题意 - 给定一个长度为 $n$ 的序列和一个整数 $p$。 - 有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p\%$ 的数。 - 输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 $\lfloor \frac{100}{p} \rfloor$。 - $n,m \le 1.5 \times 10^5$，$20 \le p \le 100$。 ## 题解 首先考虑 $p > 50$ 的情况，问题变成区间绝对众数。 对于这个问题，我们可以每次同时删除两个不同的数，则最后剩下的互不相同的数最多只有一个，这一个就是答案。 扩展到 $p \le 50$ 的情况也是这样的，我们每次同时删除 $\lfloor \frac{100}{p} \rfloor + 1$ 个互不相同的数，则最后剩下的互不相同的数最多只有 $\lfloor \frac{100}{p} \rfloor$ 个，这些数一定包含了所有答案。 由于 $p \ge 20$，因此 $\lfloor \frac{100}{p} \rfloor \le 5$，合并的部分可以当成常数。 考虑线段树维护序列，时间复杂度 $\mathcal O((n+m) \log n)$。 ## 代码 ```cpp const int N = 1.5e5 + 7; int n, m, p, k, a[N]; struct T { int l, r, z; vector<pi> c; } t[N<<2]; inline vector<pi> merge(vector<pi> a, vector<pi> b) { for (pi o : b) { bool ok = 0; for (pi &p : a) if (p.fi == o.fi) { p.se += o.se, ok = 1; break; } if (ok) continue; a.pb(o); if ((int)a.size() <= k) continue; int x = n; for (pi p : a) x = min(x, p.se); vector<pi> c; for (pi p : a) if (p.se - x) c.pb(mp(p.fi, p.se - x)); a = c; } return a; } void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if (t[p].l == t[p].r) return t[p].c.pb(mp(a[l], 1)), void(); build(ls, l, md), build(rs, md + 1, r); t[p].c = merge(t[ls].c, t[rs].c); } inline void setx(int p, int x) { t[p].z = x, t[p].c.clear(), t[p].c.pb(mp(x, t[p].r - t[p].l + 1)); } inline void spd(int p) { if (t[p].z) setx(ls, t[p].z), setx(rs, t[p].z), t[p].z = 0; } void change(int p, int l, int r, int x) { if (t[p].l >= l && t[p].r <= r) return setx(p, x); spd(p); if (l <= md) change(ls, l, r, x); if (r > md) change(rs, l, r, x); t[p].c = merge(t[ls].c, t[rs].c); } vector<pi> ask(int p, int l, int r) { if (t[p].l >= l && t[p].r <= r) return t[p].c; spd(p); vector<pi> c; if (l <= md) c = ask(ls, l, r); if (r > md) c = merge(c, ask(rs, l, r)); return c; } int main() { rd(n), rd(m), rd(p), k = 100 / p, rda(a, n); build(1, 1, n); for (int i = 1, o, l, r, x; i <= m; i++) { rd(o), rd(l), rd(r); if (o == 1) rd(x), change(1, l, r, x); else { auto ans = ask(1, l, r); print(ans.size(), ' '); for (pi o : ans) print(o.fi, ' '); prints(""); } } return 0; } ```