UVa 11297 Census 2 차원 선분 트 리 템 플 릿

제목 링크:https://vjudge.net/problem/UVA-11297
     2 차원 선분 트 리 템 플 릿 문제, 단점 수정 과 구간 조회, 여 기 는 유 여가 가 말 한 대로 build 함 수 를 추가 하여 어느 정도 최적화 효 과 를 낼 수 있 습 니 다.

#include
#include
#include
using namespace std;
const int INF = (1<<30);
const int maxn = 2000 + 10;
struct IntervalTree2D {
  int Max[maxn][maxn], Min[maxn][maxn], n, m;
  int xo, xleaf, x1, y1, x2, y2, x, y, v, vmax, vmin;

  void build1D(int o, int L, int R) {
    if(L == R) {
      if(xleaf) { scanf("%d", &v); Max[xo][o] = Min[xo][o] = v; return; }
      Max[xo][o] = max(Max[xo*2][o], Max[xo*2+1][o]);
      Min[xo][o] = min(Min[xo*2][o], Min[xo*2+1][o]);
    }
    else {
      int M = (L + R) >> 1;
      build1D(o*2, L, M);
      build1D(o*2+1, M+1, R);
      Max[xo][o] = max(Max[xo][o*2], Max[xo][o*2+1]);
      Min[xo][o] = min(Min[xo][o*2], Min[xo][o*2+1]);
    }
  }

  void build2D(int o, int L, int R) {
    if(L == R) {
      xleaf = 1;
      xo = o;
      build1D(1, 1, m);
    }
    else {
      int M = (L + R) >> 1;
      build2D(o*2, L, M);
      build2D(o*2+1, M+1, R);
      xleaf = 0; xo = o; build1D(1, 1, m);
    }
  }

  void query1D(int o, int L, int R) {
    if(y1 <= L && R <= y2) {
      vmax = max(vmax, Max[xo][o]);
      vmin = min(vmin, Min[xo][o]);
    }
    else {
      int M = (L + R) >> 1;
      if(y1 <= M) query1D(o*2, L, M);
      if(M < y2) query1D(o*2+1, M+1, R);
    }
  }

  void query2D(int o, int L, int R) {
    if(x1 <= L && R <= x2) {
      xo = o;
      query1D(1, 1, m);
    }
    else {
      int M = (L + R) >> 1;
      if(x1 <= M) query2D(o*2, L, M);
      if(M < x2) query2D(o*2+1, M+1, R);
    }
  }

  void modify1D(int o, int L, int R) {
    if(L == R) {
      if(xleaf) { Max[xo][o] = Min[xo][o] = v; return; }
      Max[xo][o] = max(Max[xo*2][o], Max[xo*2+1][o]);
      Min[xo][o] = min(Min[xo*2][o], Min[xo*2+1][o]);
    }
    else {
      int M = (L + R) >> 1;
      if(y <= M) modify1D(o*2, L, M);
      else modify1D(o*2+1, M+1, R);
      Max[xo][o] = max(Max[xo][o*2], Max[xo][o*2+1]);
      Min[xo][o] = min(Min[xo][o*2], Min[xo][o*2+1]);
    }
  }

  void modify2D(int o, int L, int R) {
     if(L == R) {
       xleaf = 1; xo = o; modify1D(1, 1, m);
     }
     else {
        int M = (L + R) >> 1;
        if(x <= M) modify2D(o*2, L, M);
        else modify2D(o*2+1, M+1, R);
        xo = o; xleaf = 0; modify1D(1, 1, m);
     }
  }

  void modify() { modify2D(1, 1, n); }
  void query() { vmax = -INF, vmin = INF; query2D(1, 1, n); }

};

IntervalTree2D t;

int main() {
  int n, m, Q, x1, y1, x2, y2, x, y, v;
  char op[10];
  scanf("%d", &n);
  m = n;
  t.n = n; t.m = n;
  t.build2D(1, 1, n);
  scanf("%d", &Q);
  while(Q--) {
    scanf("%s", op);
    if(op[0] == 'q') {
      scanf("%d%d%d%d", &t.x1, &t.y1, &t.x2, &t.y2);
      t.query();
      printf("%d %d
", t.vmax, t.vmin);
    }
    else {
      scanf("%d%d%d", &t.x, &t.y, &t.v);
      t.modify();
    }
  }
  return 0;
}