题目描述

$\mathscr{Link}$

$N\times N$ 的网格图，每个格点维护一个集合，$Q$ 次操作，每次给定一个子区间，对区间内的点的集合加入 $k_i$ 个 $c_i$。

操作后求每个点的集合的绝对众数，若没有绝对众数则输出 -1。

$N \leq 10^3, Q\leq 5\times 10^5, 1\leq k_i \leq 10^9, 1\leq c_i \leq Q$。

思路

首先想到的是摩尔投票算法，但是仍然很难处理，用扫描线加树套树可能维护。

接下来将一种简单的方法，使用二进制分组，对于每一个二进制位，$c_i$ 为 $1$ 的视为区间 $+1$，否则为区间 $-1$，若和为正数，那么说明众数这一位为 $1$，反之同理。

最后使用二维数点判断一下即可，写的二维树状数组，也可以扫一下单 $\log$。

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int, int>

using namespace std;

namespace yuyu {
    const int N = 5e5 + 1000;
    int n, q, x1[N], y1[N], x2[N], y2[N], c[N], k[N];
    vector<int> K[N];
    vector<pii> Q[N];
    int ans[1010][1010];
    struct TwoTree {
        ll tr[1010][1010];
        void add(int x, int y, int c) { 
            for (int i = x; i <= n; i += i & -i)
                for (int j = y; j <= n; j += j & -j)
                    tr[i][j] += c;
        }
        void add(int x, int y, int xx, int yy, int c) {
            add(x, y, c);
            add(xx + 1, y, -c);
            add(x, yy + 1, -c);
            add(xx + 1, yy + 1, c);
        }
        ll ask(int x, int y) {
            ll res = 0;
            for (int i = x; i; i -= i & -i)
                for (int j = y; j; j -= j & -j)
                    res += tr[i][j];
            return res;
        }
    } A, B;
    void main() {
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= q; i ++ ) {
            scanf("%d%d%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i], &c[i], &k[i]);
            K[c[i]].pb(i);
            A.add(x1[i], y1[i], x2[i], y2[i], k[i]);
        }
        for (int i = 0; i < 20; i ++ ) {
            vector<vector<ll>> b(n + 10, vector<ll>(n+10,0));
            for (int j = 1; j <= q; j ++ ) {
                if (c[j] >> i & 1) {
                    b[x1[j]][y1[j]] += k[j];
                    b[x1[j]][y2[j] + 1] -= k[j];
                    b[x2[j] + 1][y1[j]] -= k[j];
                    b[x2[j] + 1][y2[j] + 1] += k[j];
                } else {
                    b[x1[j]][y1[j]] -= k[j];
                    b[x1[j]][y2[j] + 1] += k[j];
                    b[x2[j] + 1][y1[j]] += k[j];
                    b[x2[j] + 1][y2[j] + 1] -= k[j];
                }
            }
            for (int j = 1; j <= n; j ++ )
                for (int k = 1; k <= n; k ++ )
                    b[j][k] += b[j - 1][k] + b[j][k - 1] - b[j - 1][k - 1];
            for (int j = 1; j <= n; j ++ )
                for (int k = 1; k <= n; k ++ )
                    if (b[j][k] > 0) ans[j][k] += (1 << i);
        }
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ ) {
                if (ans[i][j] <= q && ans[i][j] >= 1)
                    Q[ans[i][j]].pb({i, j});
                else ans[i][j] = -1;
            }
        for (int i = 1; i <= q; i ++ ) {
            for (int j : K[i]) B.add(x1[j], y1[j], x2[j], y2[j], k[j]);
            for (auto j : Q[i]) {
                if (B.ask(j.first, j.second) * 2 <= A.ask(j.first, j.second))
                    ans[j.first][j.second] = -1;
            }
            for (int j : K[i]) B.add(x1[j], y1[j], x2[j], y2[j], -k[j]);
        }
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                cout << ans[i][j] << " \n"[j == n];
    }
};

int main() {
    //freopen("aprilfoolsday.in", "r", stdin);
    //freopen("aprilfoolsday.out", "w", stdout);
    yuyu::main();
    return 0;
}