2018 우 객 다 교 2 차 J 팜

제목:
번역 은 다른 사람의 것 을 직접 옮 겼 다.
n * m (n * m < = 1e6) 의 농장 과 각 칸 에 있 는 식물의 종류 번 호 를 알려 줍 니 다. 8712 ° [1, n * m],
이 어 T (T < = 1e6) 차 시비 에 대한 정 보 를 드 립 니 다. 정 보 는 x1, y1, x2, y2, k (1 < = x1 & lt; = x2 & gt; = n, 1 & lt; = y1 & gt; = y2 & gt; = m, 1 & lt; = k & gt; = n * m) 를 포함 합 니 다.
좌표 (x1, y1) 에서 좌표 (x2, y2) 까지 의 구간 에 있 는 모든 식물 에 k 로 번 호 를 매 기 는 비 료 를 가 하 는 것 을 나타 낸다.
식물 은 자신의 번호 와 다른 비료 에 가 해 지면 죽는다 는 것 을 알 고 있 으 며, 모든 비 료 를 주 고 조작 하면 몇 그루 의 식물 이 죽 는 지 물 었 다.
원본 링크: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.
생각:
2 차원 트 리 / 2 차원 트 리 배열 / 또는 4 분 트 리 고려
4 분 트 리 사고방식:
4 분 트 리 원리 와 선분 트 리, push down lazy 표시 시
구간 내 에 두 가지 화학 비료 가 동시에 뿌 려 지면 레이 지 를 - 1 대표 구간 내 꽃 이 모두 죽 었 고 다른 상황 은 간단하게 분석 해 보 는 것 도 좋다.
마지막 으로 모든 push down 쪽 을 조회 하면 통계 가 됩 니 다.코드:

#include 
const int MAXN=1e6+7;
using namespace std;
int tree[MAXN*20];
int son[MAXN*20][4];
int n,m,t;
int id;
vectora[MAXN];
int stx,enx,sty,eny,v;
 
void push_down(int rt){
    if(tree[rt]==0){
        return;
    }else if(tree[rt]==-1){
        tree[son[rt][0]]=tree[son[rt][1]]=tree[son[rt][2]]=tree[son[rt][3]]=-1;
    }else{
        for(int i=0;i<4;i++){
            if(tree[son[rt][i]]==0) tree[son[rt][i]]=tree[rt];
            else if(tree[son[rt][i]]!=tree[rt]) tree[son[rt][i]]=-1;
            else continue;
        }
    }
}
void build(int lx,int rx,int ly,int ry,int rt){
    tree[rt]=0;
    if(lx==rx&&ly==ry){
 
        return ;
    }
    int midx=(lx+rx)/2;
    int midy=(ly+ry)/2;
    build(lx,midx,ly,midy,son[rt][0]=++id);
    if(ly!=ry) build(lx,midx,midy+1,ry,son[rt][1]=++id);
    if(lx!=rx) build(midx+1,rx,ly,midy,son[rt][2]=++id);
    if(ly!=ry&&lx!=rx) build(midx+1,rx,midy+1,ry,son[rt][3]=++id);
}
int query(int lx,int rx,int ly,int ry,int rt){
    if(tree[rt]==-1){
        return 0;
    }
 
    if(lx==rx&&ly==ry){
        if(tree[rt]==0||tree[rt]==a[lx][ly]){
            return 1;
        }
        return 0;
    }
    int midx=(lx+rx)/2;
    int midy=(ly+ry)/2;
    push_down(rt);
    int ans=0;
    ans+=query(lx,midx,ly,midy,son[rt][0]);
    if(ly!=ry) ans+=query(lx,midx,midy+1,ry,son[rt][1]);
    if(lx!=rx) ans+=query(midx+1,rx,ly,midy,son[rt][2]);
    if(ly!=ry&&lx!=rx) ans+=query(midx+1,rx,midy+1,ry,son[rt][3]);
    return ans;
}
void update(int lx,int rx,int ly,int ry,int rt){
    if(tree[rt]==-1||stx>rx||sty>ry||enx>n>>m>>t;id=1;
    if(n==0||m==0){cout<<0<>x;
            a[i].push_back(x);
        }
    }
 
    build(1,n,1,m,1);
    while(t--){cin>>stx>>sty>>enx>>eny>>v;
        update(1,n,1,m,1);
    }
    cout<