自动搬运

查看原文

来自洛谷，原作者为

	Egg_eating_master Always break; Never continue; | 我吃了个蛋

搬运于2025-08-24 23:11:04，当前版本为作者最后更新于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;
}