2018 우 객 다 교 훈련 - farm (2 차원 나무 모양 배열)

링크:https://www.nowcoder.com/acm/contest/140/J 우 객 망 
제목 설명
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.
 
 
입력 설명:

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.

 
예시 1
입력

2 2 2
1 2
2 3
1 1 2 2 2
2 1 2 1 1

출력

3

 n * m 의 밭 행렬 을 제시 하고 칸 마다 식물 이 심 어 져 있다.격자 에 t 번 비 료 를 주 고 한 번 에 다섯 개의 숫자 를 주 며 x1, y1, x2, y2, k, 비 료 를 주 는 지역 좌표 와 비 료 를 주 는 종류 입 니 다.식물 이 시비 종류 와 맞지 않 으 면 식물 은 죽는다.결국 몇 개의 식물 이 죽 느 냐 고 물 었 다.
생각:
  2 차원 나무 모양 배열 로 각 칸 의 시비 종류 총화 와 시비 횟수 를 유지 하고 마지막 으로 식물의 종류 * 시비 횟수 = = 시비 종류 총화, 같 으 면 이 격자 식물 은 죽지 않 는 다.그러나 한 칸 식물의 종류 가 3 이 라면 비 료 는 각각 1, 2, 4, 5 로 위의 판단 조건 을 충족 시 켰 지만 이 식물 은 죽 었 다.
  난수 로 이 문 제 를 처리 하 는 것 은 난수 분포 가 분산 되 어 있 기 때문에 위의 이런 상황 은 거의 발생 할 수 없다.

#include
using namespace std;

typedef long long ll;
const int maxn=1e6+10;

int a[maxn],cnt[maxn],ran[maxn];
ll sum[maxn];
int n,m,t,x,y,z,w,k;

int lowbit(int x){
    return x&-x;
}
void update(int x,int y,int add,int d)
{
    int tempy=y;
    while(x<=n)
    {
        y=tempy;
        while(y<=m)
        {
            sum[(x-1)*m+y-1]+=add;
            cnt[(x-1)*m+y-1]+=d;
            y+=lowbit(y);
        }
        x+=lowbit(x);
    }
}
bool query(int x,int y)
{
    ll rets=0,retc=0;
    int tmp=ran[a[(x-1)*m+y-1]];
    int tempy=y;
    while(x>0){
        y=tempy;
        while(y>0){
            rets+=sum[(x-1)*m+y-1];
            retc+=cnt[(x-1)*m+y-1];
            y-=lowbit(y);
        }
        x-=lowbit(x);
    }
    if(rets==retc*tmp) return true;
    else return false;
}
void init(){
    for(int i=0;i