题解：P11882 [RMI 2024] 彩虹糖 / Skittlez

Egg_eating_master · 2025-03-13 20:46:29 · 题解

考虑对 c 做二进制拆分。对于一个位置 (x,y)，若这个位置上的所有 c 在二进制表示下第 i 位为 p 的比较多，那么如果该位置存在绝对众数，它的二进制第 i 位一定为 p。

只要对于每个 i 都做一遍这个东西，就可以对于每一个位置得到唯一可能的绝对众数。我们接下来只要 check 它到底是不是绝对众数就可以了，选择一个你喜欢的数据结构即可，我使用了二维树状数组。

时间复杂度 O((n^2+q)\log q+(n+q)\log^2 n)，其中前半部分是得到唯一可能的答案，后半部分是 check。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1005, maxm = 500005;
int n, q;
int d[maxn][maxn][21];
int ans[maxn][maxn];
struct node {int x1, y1, x2, y2, k;};
struct heige {int x, y;};
vector<node> hg[maxm];
vector<heige> h[maxm];
struct BIT {
    int sum[maxn][maxn];
    int lowbit(int x) {return x & -x;}
    void update(int x, int y, int val) {
        for (int i = x; i <= n; i += lowbit(i))
            for (int j = y; j <= n; j += lowbit(j))
                sum[i][j] += val;
    }
    int query(int x, int y) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i))
            for (int j = y; j; j -= lowbit(j))
                res += sum[i][j];
        return res;
    }
} t;
void add(int x1, int y1, int x2, int y2, int p, int k) {d[x1][y1][p] += k; d[x1][y2 + 1][p] -= k; d[x2 + 1][y1][p] -= k; d[x2 + 1][y2 + 1][p] += k;}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        int x1, y1, x2, y2, k, c; cin >> x1 >> y1 >> x2 >> y2 >> c >> k;
        add(x1, y1, x2, y2, 0, k);
        for (int j = 1; j <= 20; j++)
            if ((c >> j - 1) & 1) add(x1, y1, x2, y2, j, k);
        hg[c].push_back((node){x1, y1, x2, y2, k});
    }
    for (int i = 0; i <= 20; i++) {
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                d[j][k][i] += d[j - 1][k][i];
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                d[j][k][i] += d[j][k - 1][i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= 20; k++)
                if (d[i][j][k] * 2 > d[i][j][0]) ans[i][j] |= (1 << k - 1);
            if (ans[i][j] > q) ans[i][j] = -1;
            else h[ans[i][j]].push_back((heige){i, j});
        }
    for (int i = 0; i <= q; i++) {
        for (auto k : hg[i]) {
            t.update(k.x1, k.y1, k.k);
            t.update(k.x1, k.y2 + 1, -k.k);
            t.update(k.x2 + 1, k.y1, -k.k);
            t.update(k.x2 + 1, k.y2 + 1, k.k);
        }
        for (auto k : h[i]) {
            int s = t.query(k.x, k.y);
            if (s * 2 <= d[k.x][k.y][0] || s == 0) ans[k.x][k.y] = -1;
        }
        for (auto k : hg[i]) {
            t.update(k.x1, k.y1, -k.k);
            t.update(k.x1, k.y2 + 1, k.k);
            t.update(k.x2 + 1, k.y1, k.k);
            t.update(k.x2 + 1, k.y2 + 1, -k.k);
        }
    }
    for (int i = 1; i <= n; i++, cout << '\n')
        for (int j = 1; j <= n; j++)
            cout << ans[i][j] << ' ';
    return 0;
}