우 객 다 교 2 차 J 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 크기 의 농토 가 있 는데 땅 마다 a [i] [j] 의 종류 가 심 어 져 있다. 그 다음 에 T 번 농약 을 뿌 려 야 한다. 매번 왼쪽 상단 (x1, y1), 오른쪽 하단 (x2, y2) 의 행렬 에 k 의 농약 을 뿌 려 야 한다. 뿌 려 진 식물의 종류 와 농약 의 종류 가 다 르 면 (즉 a [i] [j]! = k) 이 식물 은 죽는다.T 차 분사 후 이 n * m 개 식물 이 몇 개 죽 었 냐 고 물 었 다.
제목 사고: 한 식물 이 죽 는 조건 은 이 식물 이 그 종류 와 다른 농약 을 뿌 렸 다 는 것 이다. 그러면 우 리 는 뿌 릴 때 먼저 모든 농약 을 범위 에 따라 뿌 린 다음 에 i 종 식물 에 대해 우 리 는 i 종 농약 분사 효 과 를 제거 한 다음 에 이 식물 이 다른 농약 에 뿌 렸 는 지 조회 할 수 있다.(즉 0 보다 큰 지 여부) 제거 효 과 를 더 하면 됩 니 다. 식물의 종 류 는 n * m = 1e6 가지 가 많 기 때문에 서로 다른 종류의 식물의 좌표 와 농약 의 커버 범 위 를 vector 로 저장 하 는 것 을 고려 할 수 있 습 니 다. 행렬 커버 와 삭제 작업 은 2 차원 나무 모양 배열 을 통 해 이 루어 집 니 다. 시간 복잡 도 는 대략 (nm + T) log (nm) log (nm) log (nm) 입 니 다.(사내 들 은 모두 하나의 log 방법 으로 공부 해 야 한다. orz...)
구체 적 으로 코드 보기:

#include 
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pb push_back
#define MP make_pair
#define lowbit(x) x&-x
#define FIN freopen("in.txt","r",stdin)
#define fuck(x) cout<pii;
const int MX=1e6+7;

int n,m,t;
vectorbit[MX];
vectorpoint[MX];
inline void add(int x,int y,int z){
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=m;j+=lowbit(j))
            bit[i][j]+=z;
    }
}
inline void update(int x1,int Y1,int x2,int y2,int z){
    add(x1,Y1,z);add(x2+1,y2+1,z);
    add(x1,y2+1,-z);add(x2+1,Y1,-z);
}
inline int query(int x,int y){
    int res=0;
    for(int i=x;i;i-=lowbit(i)){
        for(int j=y;j;j-=lowbit(j))
            res+=bit[i][j];
    }
    return res;
}
struct que{
    int a,b,c,d;
};
vectorq[MX];

int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++) bit[i].resize(m+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int z;
            scanf("%d",&z);
            point[z].pb(MP(i,j));
        }
    }
    for(int i=1;i<=t;i++){
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        update(a,b,c,d,1);
        q[k].pb(que{a,b,c,d});
    }
    int ans=0;
    for(int i=1;i<=n*m;i++){
        if(point[i].size()){
            for(auto nw:q[i])
                update(nw.a,nw.b,nw.c,nw.d,-1);
            for(auto nw:point[i]){
                if(query(nw.fi,nw.se)) ans++;
            }
            for(auto nw:q[i])
                update(nw.a,nw.b,nw.c,nw.d,1);
        }

    }
    printf("%d
",ans);
    return 0;
}