Cut and Stick

timudayi

链接：https://codeforces.com/problemset/problem/1514/D

题目大意

给定一个长为n的序列a，有q次询问，每次询问给定一个区间$[l, r]$，问最少要将这个区间划分多少次（不一定连续），使得每个划分（假设长度为len）里众数的个数f满足：$f\leq \lceil \frac {len} 2 \rceil$。

题目分析

如果对于$[l,r]$，众数个数已经小于等于$\lceil \frac{len} 2 \rceil$，那么就不用再划分子了。

否则，就存在这样一种构造法：

假设众数个数为f，那么就剩下的数有len-f个，这些len-f个非众数数可以和len-f+1个众数一起划分到一个子区间中。剩下的众数就单独划分到一个集合中，总共需要$1+f-(len-f+1)=2*f-len$个划分。

那么现在的问题就是怎么快速求众数了。

一般来说，要使用莫队算法。但是在这道题中，出现次数未超过$\lceil \frac{len} 2 \rceil$的众数并没有意义，所以我们也可以用主席树求。具体看代码，时间复杂度$O(n\log n)$。

AC代码

#include "bits/stdc++.h"

using namespace std;
const int N = 3e5 + 10;

struct Tree {
    int *sum, *ls, *rs;
    int n, cnt;

    Tree(int n) {
        sum = new int[n << 5];
        ls = new int[n << 5];
        rs = new int[n << 5];
        cnt = 0;
    }

    int build(int l, int r) {
        int rt = ++cnt;
        sum[rt] = 0;
        if (l < r) {
            int mid = (l + r) >> 1;
            ls[rt] = build(l, mid);
            rs[rt] = build(mid + 1, r);
        }

        return rt;
    }

    int update(int pre, int l, int r, int x) {
        int rt = ++cnt;
        ls[rt] = ls[pre], rs[rt] = rs[pre], sum[rt] = sum[pre] + 1;
        if (l < r) {
            int mid = (l + r) >> 1;
            if (x <= mid) ls[rt] = update(ls[pre], l, mid, x);
            else rs[rt] = update(rs[pre], mid + 1, r, x);
        }

        return rt;
    }

    // 查找有没有大于一半的
    int query(int u, int v, int l, int r, int lim) {
        if (l >= r) return sum[v] - sum[u];
        if (sum[v] - sum[u] <= lim) return 0;
        int x = sum[ls[v]] - sum[ls[u]], y = sum[rs[v]] - sum[rs[u]];

        int mid = (l + r) >> 1;
        int res;
        if (x > lim && (res = query(ls[u], ls[v], l, mid, lim)) > lim) return res;
        if (y > lim && (res = query(rs[u], rs[v], mid + 1, r, lim)) > lim) return res;
        return 0;
    }
};

int n, q, m;
int a[N], b[N], rt[N];

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        b[i] = a[i];
    }

    sort(b + 1, b + 1 + n);
    m = unique(b + 1, b + 1 + n) - (b + 1);

    Tree t(N);
    rt[0] = t.build(1, m);
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(b + 1, b + 1 + m, a[i]) - b;
        rt[i] = t.update(rt[i - 1], 1, m, p);
    }

    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        int lim = ceil((r - l + 1.0) / 2);
        int f = t.query(rt[l - 1], rt[r], 1, m, lim);

        printf("%d\n", max(1, 2 * f - (r - l + 1)));
    }
}