(UVA) 11297 - Census [樹套樹 求 max, min]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2272&mosmsg=Submission+received+with+ID+17747368

基本上的想法是 樹套樹 啦。

簡單來講，在一棵正常的segment tree(維護x軸 的 min&max)中，在塞一棵segment tree(維護y軸的)。那有一個小細節要注意，在modify裡面中！

好累喔，不太想打XD

#include <iostream>
#include <stdio.h>
#include <utility>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 503;
const int INF = 1e9+7;

int n;

pii operator+(const pii &p1,const pii &p2) {
 return make_pair(max(p1.first,p2.first),min(p1.second,p2.second));
}

struct Node2 {
 Node2* lc;
 Node2* rc;
 pii val;
 Node2() {
  lc=rc=NULL;
  val=make_pair(-INF,INF);
 }
 void pull() {
  val= lc->val + rc->val;
 }
};

Node2* Build2(int L,int R) {
 Node2* node = new Node2();
 if (L==R) return node;
 int mid=(L+R)>>1;
 node->lc=Build2(L,mid);
 node->rc=Build2(mid+1,R);
 return node;
}

struct Node {
 Node* lc;
 Node* rc;
 Node2* c;
 Node(int n) {
  lc=rc=NULL;
  c = Build2(1,n);
 }
};

Node* root;

Node* Build1(int L,int R,int n) {
 Node* node = new Node(n);
 if (L==R) return node;
 int mid=(L+R)>>1;
 node->lc=Build1(L,mid,n);
 node->rc=Build1(mid+1,R,n);
 return node;
}

pii query1(Node* node,int n,int L,int R,int l,int r,int qy1,int qy2);

void modify2(Node2* node,int L,int R,int pos,int val,int x1,int x2,int qx) {
// cout<<"in 2 : "<<L<<" ~ "<<R<<endl;
 if (L==R) {
  if (x1!=x2) {
   node->val = query1(root,n,1,n,x1,qx-1,pos,pos) + query1(root,n,1,n,qx+1,x2,pos,pos) + make_pair(val,val);
  }
  else if (x1==x2){
   node->val = make_pair(val,val);
  }
  return;
 }
 int mid=(L+R)>>1;
 if (pos<=mid) modify2(node->lc,L,mid,pos,val,x1,x2,qx);
 else modify2(node->rc,mid+1,R,pos,val,x1,x2,qx);
 node->pull();
 return;
}

void modify1(Node* node,int n,int L,int R,int qx,int qy,int val) {
 modify2(node->c,1,n,qy,val,L,R,qx);
 if (L==R) {
  return;
 }
 int mid=(L+R)>>1;
 if (qx<=mid) modify1(node->lc,n,L,mid,qx,qy,val);
 else modify1(node->rc,n,mid+1,R,qx,qy,val);
 return;
}

pii query2(Node2* node,int L,int R,int l,int r) {
// cout<<"in 2 : "<<L<<" ~ "<<R<<endl; 
 if (L>r || l>R) return make_pair(-INF,INF);
 else if (l<=L && R<=r) return node->val;
 int mid=(L+R)>>1;
 return query2(node->lc,L,mid,l,r) + query2(node->rc,mid+1,R,l,r);
}

pii query1(Node* node,int n,int L,int R,int l,int r,int qy1,int qy2) {
// cout<<"in 1 : "<<L<<" ~ "<<R<<endl; 
 if (l>R || L>r) return make_pair(-INF,INF);
 else if (l<=L && R<=r) return query2(node->c,1,n,qy1,qy2);
 int mid=(L+R)>>1;
 return query1(node->lc,n,L,mid,l,r,qy1,qy2) + query1(node->rc,n,mid+1,R,l,r,qy1,qy2);
}

int main () {
// freopen("output.txt","w",stdout);
 while (scanf("%d",&n) != EOF) {
  root=Build1(1,n,n);
  for (int x=1;n>=x;x++) {
   for (int y=1;n>=y;y++) {
    int i;
    scanf("%d",&i);
    modify1(root,n,1,n,x,y,i);
//    cout<<"get = "<<query1(root,n,1,n,x,x,y,y).first<<' '<<query1(root,n,1,n,x,x,y,y).second<<endl;;
   }
  }
  int m;
  scanf("%d",&m);
  while (m--) {
   getchar();
   char i;
   scanf("%c",&i);
   if (i=='q') {
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    pii ret=query1(root,n,1,n,a,c,b,d);
    printf("%d %d\n",ret.first,ret.second);
   }
   else if (i=='c') {
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    modify1(root,n,1,n,a,b,c);
   }
  }
 }
}

/*
5
1 2 3 4 5
0 9 2 1 3
0 2 3 4 1
0 1 2 4 5
8 5 3 1 4
4
q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2

10
98 14 55 72 2 15 19 54 32 58
60 35 46 96 44 70 3 76 58 11
34 65 48 45 49 17 74 51 25 68
82 76 34 37 0 37 4 19 43 37
29 3 72 75 0 68 45 55 44 56
18 31 73 18 28 74 36 2 25 13
22 60 41 57 49 41 46 54 13 89
43 42 92 67 70 44 88 67 52 32
75 70 63 0 41 91 74 77 45 0
42 20 12 84 77 61 77 75 67 90
50
c 6 3 8
c 6 8 18
c 3 8 2
q 3 7 8 7
q 6 10 8 10
q 9 2 9 2
q 3 10 10 10
c 4 4 66
c 5 9 66
q 1 10 6 10
q 5 10 8 10
q 4 4 10 9
q 1 3 2 3
c 7 7 39
q 6 3 8 4
c 1 1 81
c 9 10 35
c 10 3 1
c 5 3 74
c 8 8 83
c 8 9 4
*/