基本上的想法是 樹套樹 啦。
簡單來講，在一棵正常的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 */
