题解 CF643G 【Choosing Ads】

xht · 2020-03-03 19:52:51 · 题解

CF643G Choosing Ads

题意

• 给定一个长度为 n 的序列和一个整数 p。
• 有 m 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 p\% 的数。
• 输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 \lfloor \frac{100}{p} \rfloor。

题解

首先考虑 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;
}