一、题意
White Rabbit has a rectangular farmland of n*m. In each of the grid there is a kind of plant. The plant in the j-th column of the i-th row belongs the a[i][j]-th type.
White Cloud wants to help White Rabbit fertilize plants, but the i-th plant can only adapt to the i-th fertilizer. If the j-th fertilizer is applied to the i-th plant (i!=j), the plant will immediately die.
Now White Cloud plans to apply fertilizers T times. In the i-th plan, White Cloud will use k[i]-th fertilizer to fertilize all the plants in a rectangle [x1[i]...x2[i]][y1[i]...y2[i]].
White rabbits wants to know how many plants would eventually die if they were to be fertilized according to the expected schedule of White Cloud.
White Cloud wants to help White Rabbit fertilize plants, but the i-th plant can only adapt to the i-th fertilizer. If the j-th fertilizer is applied to the i-th plant (i!=j), the plant will immediately die.
Now White Cloud plans to apply fertilizers T times. In the i-th plan, White Cloud will use k[i]-th fertilizer to fertilize all the plants in a rectangle [x1[i]...x2[i]][y1[i]...y2[i]].
White rabbits wants to know how many plants would eventually die if they were to be fertilized according to the expected schedule of White Cloud.
简单的说就是，给定一个大型矩形，矩形中每个格子对应一个单独的数字。之后K个命令给，要求大矩阵中某些子矩形的各个元素的赋予统一值，求在命令结束后还保持原有值的个数。其中矩阵的格子总数不超过1e6，但是不指定长宽。
二、解题思路
要求使用一种数据结构进行批量染色操作，且要求后面可以检测是否被"其他颜色污染"。
则看了题解很容易想到，使用某种数据结构做批量增加的操作，之后检测增加后的值是否能够整除原来的元素。
考虑如果直接按照1、2、3、4进行赋值就会有：同样是染色2次，有3+3 = 6和2+2+2 = 6，无法有效判断整除。考虑加一个操作：增加染色次数的判定，但是同样也会有3+3 = 6 = 2+4的问题，因此对数组进行重新设计，则直觉告诉我们，1，2，4，7，......an,an+n这个数列可以完美解决这个问题——不存在第2种组合可以使用相同数目的数列元素相加得到数列的某个其他元素。
因此，使用一位数组开足够大的数组之后，动态的按照二维数组的方式进行寻址，即可完成上述操作。
#include<bits/stdc++.h>
using namespace std; #define ll intmax_t const int MAXN=; ll mapp[MAXN];
ll farm[MAXN];
ll times[MAXN];
ll color[MAXN]; int maxx_numebr = ;
int add_number = ; int m,n,k; void insert_mex(ll *v,int a,int b,ll key)
{
a+=;
b+=;
while(a<n+)
{
int num = a*(m+);
int pos = b;
while(pos<m+)
{
v[num+pos] += key;
pos+= pos&(-pos);
}a+=a&(-a); }
}
ll find_mex(ll *v,int a,int b)
{
a+=;
b+=;
ll cntt = ;
while(a)
{
int num = a*(m+);
int pos = b;
while(pos)
{
cntt += v[num+pos];
pos -= pos&(-pos);
}
a-=a&(-a);
}
return cntt;
} void insert(ll *v,int a,int b,int c,int d,ll key)
{
// cout<<"coor :"<<a<<" "<<b<<endl;
// cout<<"coor :"<<a<<" "<<d<<endl;
// cout<<"coor :"<<c<<" "<<b<<endl;
// cout<<"coor :"<<c<<" "<<d<<endl; insert_mex(v,a,b,key);
insert_mex(v,c,d,key);
insert_mex(v,a,d,-key);
insert_mex(v,c,b,-key);
} ll find(ll *v,int a,int b)
{
ll cntt = ;
cntt += find_mex(v,a,b);
return cntt;
} void init()
{
memset(color,-,sizeof(color));
for(int i=;i<n;++i)
{
int pos = i*m;
for(int j=;j<m;++j)
{
// int ppos = pos +j;
scanf("%d",&mapp[pos]);
if(color[pos] == -)color[mapp[pos]] = (maxx_numebr += (add_number++));
pos++;
}
}
for(int i=;i<k;++i)
{
int a,b,c,d,kk;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&kk);
if(color[kk] == -)color[kk] = (maxx_numebr += add_number++ );
ll key = color[kk];
a--;b--;
insert(farm,a,b,c,d,key);
insert(times,a,b,c,d,);
}
int cntt = n*m;
int pos = ;
for(int i=;i<n;++i)
{
for(int j=;j<m;++j)
{
// int pos = i*(m+23)+j;
ll kk = color[mapp[pos]];
int time_now = find(times,i,j);
ll res = find(farm,i,j);
// cout<<"check: "<<i<<" "<<j<<" times: "<<time_now<<" color "<<mapp[pos]<<endl;
if(time_now == || res == time_now*kk)cntt--;
pos++;
}
}
cout<<cntt<<endl; } int main()
{
cin>>n>>m>>k;
init(); return ;
}