CF643G Choosing Ads 题解

CF643G Choosing Ads

题意

• 给定一个长度为 $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)$。

代码

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;
}