[POI2006] TET-Tetris 3D

제목 설명:
데이터 구 조 를 작성 합 니 다. 사각형 의 최대 값 을 조회 하고 이 사각형 의 값 을 모두 이 최대 값 에 상수 로 바 꿀 수 있 습 니 다.
제목 분석:
2 차원 선분 트 리 + 영구 화 maxi 는 하위 트 리 의 최대 값 을 표시 합 니 다. tag 는 하위 트 리 가 모두 덮어 쓰 인 값 을 표시 합 니 다.
제목 링크:
Luogu 3437
Ac 코드:

#include 
#include 
#include 
#include 
int Maxx,Maxy,n;
struct inside_seg{
    int maxi[4005],tag[4005];
    void modify(int o,int l,int r,int ql,int qr,int k)
    {
        maxi[o]=std::max(maxi[o],k);
        if(ql<=l&&r<=qr) return (void)(tag[o]=std::max(tag[o],k));
        int mid=(l+r)>>1;
        if(ql<=mid) modify((o<<1),l,mid,ql,qr,k);
        if(qr>mid) modify((o<<1)|1,mid+1,r,ql,qr,k);
    }
    int ask(int o,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr) return std::max(tag[o],maxi[o]);
        int mid=(l+r)>>1;
        int ans=tag[o];
        if(ql<=mid) ans=std::max(ans,ask((o<<1),l,mid,ql,qr));
        if(qr>mid) ans=std::max(ans,ask((o<<1)|1,mid+1,r,ql,qr));
        return ans;
    }
};
struct external_seg{
    inside_seg maxi[4005],tag[4005];
    void modify(int o,int l,int r,int ql,int qr,int y1,int y2,int k)
    {
        maxi[o].modify(1,0,Maxy,y1,y2,k);
        if(ql<=l&&r<=qr) return (void)(tag[o].modify(1,0,Maxy,y1,y2,k));
        int mid=(l+r)>>1;
        if(ql<=mid) modify((o<<1),l,mid,ql,qr,y1,y2,k);
        if(qr>mid) modify((o<<1)|1,mid+1,r,ql,qr,y1,y2,k);
    }
    int ask(int o,int l,int r,int ql,int qr,int y1,int y2)
    {
        if(ql<=l&&r<=qr) return maxi[o].ask(1,0,Maxy,y1,y2);
        int mid=(l+r)>>1;
        int ans=tag[o].ask(1,0,Maxy,y1,y2);
        if(ql<=mid) ans=std::max(ans,ask((o<<1),l,mid,ql,qr,y1,y2));
        if(qr>mid) ans=std::max(ans,ask((o<<1)|1,mid+1,r,ql,qr,y1,y2));
        return ans;
    }
}T;
int main()
{
    scanf("%d%d%d",&Maxx,&Maxy,&n);
    for(int i=1,d,s,h,x,y;i<=n;i++)
    {
        scanf("%d%d%d%d%d",&d,&s,&h,&x,&y);
        h+=T.ask(1,0,Maxx,x,x+d-1,y,y+s-1);
        T.modify(1,0,Maxx,x,x+d-1,y,y+s-1,h);
    }
    printf("%d
",T.ask(1,0,Maxx,0,Maxx,0,Maxy));
    return 0;
}