J-farm

思路：随机算法，二维BIT

一开始考虑的做法和题解的随机做法想的一样，但是没想到离散化...我都不知道那几个小时在干嘛。

对于每一个权值的化肥，我们随意rand一个值，每次操作的时候这个区间就加上这个值。如果最后对于i,j。倘若cnt[i][j]*mp[a[i][j]]==v[i][j]。 那么在很大程度上可以确定，都是一个种类的化肥，该植物不会死

在这种Full-Back机制下的比赛，随机算法是很优秀的做法。打多了cf这种有HACK机制的比赛，很多时候忽略了随机算法的作用

关于二维BIT的区间更新，有2种写法，个人建议用下面的板子用差分标记，再去O(n*m)求SUM。 倘若用另一种板子，复杂度O(n*m*(logn)*(logn))T了。

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int MOD=1e9+7;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int n,m,T;
//int a[N];
int mp[N];
vector<int> a[N];
vector<ll> sum[N];
vector<int> cnt[N];
void add(int x,int y,int val,int v2){  // 更新
//    cout <<"here" << endl;
            sum[x][y]+=val,cnt[x][y]+=v2;
}
 
ll getsum(int x,int y){ // 单点求值 等价 求区间前缀和
    ll res=0;
    for(int i=x;i;i-=i&(-i))
        for(int j=y;j;j-=j&(-j))
            res+=sum[i][j];
    return res;
}
 
void update(int x1,int y1,int x2,int y2,int val,int v2){
    add(x1,y1,val,v2);// 结论
    add(x2+1,y2+1,val,v2);
    add(x1,y2+1,-val,-v2);
    add(x2+1,y1,-val,-v2);
 
}
int main(void){
    sf(n);sf(m);sf(T);
 
 
    for(int i=0;i<=n+5;i++)   a[i].resize(m+5),cnt[i].resize(m+5),sum[i].resize(m+5);
//    for(int i=0;i<=0;i++){
//        for(int j=0;j<=m+4;j++)   sum[i][j]=cnt[i][j]=0;
//    }
//    cout <<"here" << endl;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)   sum[i][j]=cnt[i][j]=0,sf(a[i][j]);
    for(int i=1;i<=n*m;i++) mp[i]=i;
    random_shuffle(mp+1,mp+1+n*m);
    for(int i=1;i<=T;i++){
        int x1,y1,x2,y2,k;
        sf(x1),sf(y1),sf(x2),sf(y2),sf(k);
        update(x1,y1,x2,y2,mp[k],1);
    }
    int ans=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
//                cout <<i <<" "<<j<<endl;
            sum[i][j]=sum[i][j]-sum[i-1][j-1]+sum[i][j-1]+sum[i-1][j];
            cnt[i][j]=cnt[i][j]-cnt[i-1][j-1]+cnt[i][j-1]+cnt[i-1][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(sum[i][j]==1ll*mp[a[i][j]]*cnt[i][j])   ans++;
        }
    }
    printf("%lld\n",1ll*n*m-ans);
 
    return 0;
}