C80 二维线段树+标记永久化 区修+区查 P3437 [POI2006] TET-Tetris 3D

// 二维线段树+标记永久化 区修+区查  空间：O(D*4*D*4) 时间：O(N*logD*logS)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ls u<<1
#define rs u<<1|1
#define mid (l+r>>1)
const int M=4005;
int D, S, N;struct segY{ //内树
  int mx[M], tag[M]; //区间最值, 永久标记
  void change(int u, int l, int r, int y1, int y2, int h){ //内修
    mx[u]=max(mx[u], h); //经过则更新mx
    if(y1<=l&&r<=y2){tag[u]=max(tag[u], h);return;}//覆盖则更新tag
    if(y1<=mid) change(ls, l, mid, y1, y2, h);
    if(y2>mid) change(rs, mid+1, r, y1, y2, h);
  }
  int query(int u, int l, int r, int y1, int y2){ //内查
    if(y1<=l&&r<=y2) return mx[u]; //覆盖则返回mx
    int ans=tag[u]; //先取tag,再裂开找
    if(y1<=mid) ans=max(ans, query(ls, l, mid, y1, y2));
    if(y2>mid) ans=max(ans, query(rs, mid+1, r, y1, y2));
    return ans;
  }
}mx[M], tag[M]; //外树每个节点维护两颗内树mx, tag

void change(int u, int l, int r, int x1, int x2, int y1, int y2, int h){ //外修
  mx[u].change(1, 1, S, y1, y2, h); //经过则入内树mx
  if(x1<=l&&r<=x2){tag[u].change(1, 1, S, y1, y2, h);return;}//覆盖则入内树tag
  if(x1<=mid) change(ls, l, mid, x1, x2, y1, y2, h);
  if(x2>mid) change(rs, mid+1, r, x1, x2, y1, y2, h);
}
int query(int u, int l, int r, int x1, int x2, int y1, int y2){ //外查
  if(x1<=l&&r<=x2) return mx[u].query(1, 1, S, y1, y2); //覆盖则入内树mx
  int ans=tag[u].query(1, 1, S, y1, y2); //先入内树tag,再裂开找
  if(x1<=mid) ans=max(ans, query(ls, l, mid, x1, x2, y1, y2));
  if(x2>mid) ans=max(ans, query(rs, mid+1, r, x1, x2, y1, y2));
  return ans;
}
int main(){
  scanf("%d%d%d", &D, &S, &N); int d, s, h, x, y;
  while(N--){
    scanf("%d%d%d%d%d", &d, &s, &h, &x, &y); ++x; ++y; //偏移
    h += query(1, 1, D, x, x+d-1, y, y+s-1); //累计当前区间高度
    change(1, 1, D, x, x+d-1, y, y+s-1, h); //更新当前区间高度
  }
  printf("%d\n", mx[1].mx[1]);
  return 0;
}