farm
The first line of input contains 3 integers n,m,T(n*m<=1000000,T<=1000000)
For the next n lines, each line contains m integers in range[1,n*m] denoting the type of plant in each grid.
For the next T lines, the i-th line contains 5 integers x1,y1,x2,y2,k(1<=x1<=x2<=n,1<=y1<=y2<=m,1<=k<=n*m)
Print an integer, denoting the number of plants which would die.
2 2 2 1 2 2 3 1 1 2 2 2 2 1 2 1 1
3
题意：n*m的矩阵里，每个格子都有一个数，有t次操作，每次都会选一个小矩形区域并且选择一个数x，这个小矩形区域里的数要是不等于x，这个数就会消失，问最后有多少个数会消失。
反过来想，这个数要是不消失，那么一旦这个数被选中，x肯定是等于这个数的。若把每一次的操作变成给矩形区域里都加上数x，那么最后若一个格子里的总和可以整除格子里的数，这个数则会有很大概率不消失。
于是考虑给矩阵里的数重新分配权值，且每次操作的x值也变为新的权值，这样就会很大概率避免错误情况。
#include<bits/stdc++.h> #define N 1000100 using namespace std; vector<int>Map[N]; vector<long long>dis[N]; int Rand[N]; int main() { int n,m,t; scanf("%d %d %d",&n,&m,&t); for(int i=1;i<=n;i++) { Map[i].push_back(0); dis[i].push_back(0); for(int j=1;j<=m;j++) { int a; scanf("%d",&a); Map[i].push_back(a); dis[i].push_back(0); } } srand(time(0)); for(int i=1;i<=n*m;i++)Rand[i]=rand()*rand()%9000000+rand(); while(t--) { int a,b,c,d,k; scanf("%d %d %d %d %d",&a,&b,&c,&d,&k); dis[a][b]+=Rand[k]; if(c+1<=n) dis[c+1][b]-=Rand[k]; if(d+1<=m)dis[a][d+1]-=Rand[k]; if(c+1<=n&&d+1<=m) dis[c+1][d+1]+=Rand[k]; } for(int i=1;i<=n;i++) { long long now=0; for(int j=1;j<=m;j++) { now+=dis[i][j]; if(i-1>=1) dis[i][j]=dis[i-1][j]+now; else dis[i][j]=now; } } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(dis[i][j]%Rand[Map[i][j]]!=0)ans++; printf("%d",ans); return 0; }
原文：https://www.cnblogs.com/tian-luo/p/9426758.html
