转载请注明出处:http://tokitsukaze.live/

题目链接:https://www.nowcoder.com/acm/contest/140/J


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


题解:
now[i][j]表示在T次操作后,第(i,j)个格子放的数的和。
cnt[i][j]表示在T次操作后,第(i,j)个格子被更新的次数。
v[i][j]表示第(i,j)个格子的初始值。
now和cnt用二维前缀和更新。
那么答案就是now[i][j]!=cnt[i][j]*v[i][j]的个数。

很明显这是假算法,出题人会构造数据卡你。
所以对初始值随机打乱一下,被卡的概率就很低。
复杂度O(n*m)。

代码:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-4;
const int MAX=1e6+10;
const ll mod=1e9+7;
/**************************************** head ****************************************/
VI v[MAX],cnt[MAX];
VL now[MAX];
int mp[MAX];
int main()
{
int n,m,q,i,j,x1,x2,y1,y2,vv;
while(~scanf("%d%d%d",&n,&m,&q))
{
for(i=1;i<=n*m;i++) mp[i]=i;
random_shuffle(mp+1,mp+1+n*m);
for(i=0;i<=n+1;i++)
{
v[i].resize(m+5);
cnt[i].resize(m+5);
now[i].resize(m+5);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&v[i][j]);
v[i][j]=mp[v[i][j]];
now[i][j]=0;
cnt[i][j]=0;
}
}
while(q--)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&vv);
now[x1][y1]+=mp[vv];
now[x1][y2+1]-=mp[vv];
now[x2+1][y1]-=mp[vv];
now[x2+1][y2+1]+=mp[vv];
cnt[x1][y1]++;
cnt[x1][y2+1]--;
cnt[x2+1][y1]--;
cnt[x2+1][y2+1]++;
}
int ans=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
now[i][j]+=now[i-1][j]+now[i][j-1]-now[i-1][j-1];
cnt[i][j]+=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
if(now[i][j]!=1LL*cnt[i][j]*v[i][j]) ans++;
}
}
printf("%d\n",ans);
}
return 0;
}