hyz's blog
0%

2018牛客多校第二场J题 farm

发表于

题意

有一个$$ nm(nm<=1e6) $$的矩形,每个位置有一个数。有$$ T(T<=1e6) $$次操作,每次往一个子矩形的每个格子中放入一个数。
求有多少个格子中被放入了至少一个与对应位置不相同的数。

分析

官方题解：
先考虑一个特殊的情况:矩形中的数和T次操作放的数都为0或1。
对于这种情况,我们只需要用矩阵前缀和统计一下每个格子被多少个0覆盖,被多少个1覆盖。
如果一个格子的数为0且被放入了至少一个1或这个格子的数位1且被放入了至少一个0则就会对答案产生贡献。
然后考虑原问题。
如果某个格子的数是i,而它被放入了至少一个j,且i!=j,则需要统计进入答案。
注意到,i!=j则i和j至少有一个二进制位不相同。
我们枚举0~19的每一个二进制位,然后把所有数字按照这一位是0还是1划分成两个集合,就变成了上述
特殊情况的问题。一个格子只要至少在某一个二进制位的子问题时被统计进入答案,就加到总答案中去。
复杂度 $O((nm+T)log(nm)) $

官方题解说得很清楚了，直接实现就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+9;
const double Eps=1e-7;
 
int n, m, T, a[N], x, y, xx, yy, k, num[N][20][2], ans;
 
int id(int x, int y) {
    if(x == 0 || y == 0) return 0;
    return (x - 1) * m + y;
}
 
int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d", &n, &m, &T)) {
        ans = 0;
        memset(num, 0, sizeof num);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                scanf("%d", &a[id(i, j)]);
        while(T--) {
            scanf("%d%d%d%d%d", &x, &y, &xx, &yy, &k);
            for(int bit = 0; bit < 20; bit++) {
                num[id(x, y)][bit][k >> bit & 1]++;
                if(yy + 1 <= m) num[id(x, yy + 1)][bit][k >> bit & 1]--;
                if(xx + 1 <= n) num[id(xx + 1, y)][bit][k >> bit & 1]--;
                if(xx + 1 <= n && yy + 1 <= m) num[id(xx + 1, yy + 1)][bit][k >> bit & 1]++;
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                bool flag = false;
                for(int bit = 0; bit < 20; bit++) {
                    num[id(i, j)][bit][0] += num[id(i - 1, j)][bit][0] + num[id(i, j - 1)][bit][0] - num[id(i - 1, j - 1)][bit][0];
                    num[id(i, j)][bit][1] += num[id(i - 1, j)][bit][1] + num[id(i, j - 1)][bit][1] - num[id(i - 1, j - 1)][bit][1];
                    if((a[id(i, j)] >> bit & 1 && num[id(i, j)][bit][0]) || (!(a[id(i, j)] >> bit & 1) && num[id(i, j)][bit][1]))
                        flag = true;
                }
                if(flag)
                    ans++;
            }
        }
        printf("%d\n", ans);
    }
 
    return 0;
}