hdu 4819 2013 Asia Regional Changchun G (四叉树|| 二维线段树单点更新 模板题)
http://acm.hdu.edu.cn/showproblem.php?pid=4819
题意：
给你一个n*n的矩阵， 每个点是一个数字， Q个操作，每次选择一个子矩阵， 把中心元素替换成子矩阵中最大值和最小值之和的二分之一。
思路:
显然是一个二维线段树.....
然而菜鸡如我，并没有写过二维线段树啊？
那怎么办呢
一首《凉凉》送给自己
然而我们还有四叉树2333
2A，写错一个地方。第一次写四叉树，orz
1#include <bits/stdc++.h>
2#define ms(a,x) memset(a,x,sizeof(a))
3#define lowbit(x) (x&(-x))
4using namespace std;
5typedef long long LL;
6const double eps = 1e-8;
7const double PI = acos(-1.0);
8const int N=805;
9int n;
10int a[N][N];
11struct Tree
12{
13 int mn,mx;
14 Tree()
15 {
16 mn = 1E9;
17 mx = 0;
18 }
19 void init()
20 {
21 mn = 1E9;
22 mx = 0;
23 }
24}tree[N*10000];
25int _max( int a,int b,int c,int d)
26{
27 int ret = max(a,b);
28 ret = max(ret,c);
29 ret = max(ret,d);
30 return ret;
31}
32int _min( int a,int b,int c,int d)
33{
34 int ret = min(a,b);
35 ret = min(ret,c);
36 ret = min(ret,d);
37 return ret;
38}
39void PushUp( int rt)
40{
41// cout<<"rt:"<<rt<<endl;
42 tree[rt].mn = _min(tree[rt*4+1].mn,tree[rt*4+2].mn,tree[rt*4+3].mn,tree[rt*4+4].mn);
43 tree[rt].mx = _max(tree[rt*4+1].mx,tree[rt*4+2].mx,tree[rt*4+3].mx,tree[rt*4+4].mx);
44}
1void insert( int idx,int lx,int rx,int ly,int ry,int X,int Y,int val)
2{
3// cout<<"val:"<<val<<endl;
4 if (lx==rx&&ly==ry)
5 {
6 tree[idx].mn = tree[idx].mx = val;
7// cout<<"fuck"<<" val:"<<val<<" mn:"<<tree[idx].mn <<" mx:"<<tree[idx];
8 return;
9 }
10 int mx = (lx+rx) >> 1;
11 int my = (ly+ry) >> 1;
12 if (X<=mx&&Y<=my) insert(idx*4+1,lx,mx,ly,my,X,Y,val);
13 if (X<=mx&&Y>=my+1) insert(idx*4+2,lx,mx,my+1,ry,X,Y,val);
14 if (X>=mx+1&&Y<=my) insert(idx*4+3,mx+1,rx,ly,my,X,Y,val);
15 if (X>=mx+1&&Y>=my+1) insert(idx*4+4,mx+1,rx,my+1,ry,X,Y,val);
16// puts("miao");
17 PushUp(idx);
18}
19int queryMN( int idx,int lx,int rx,int ly,int ry,int Lx,int Rx,int Ly,int Ry)
20{
21 if (Lx<=lx && Rx>=rx && Ly<=ly && Ry>=ry) return tree[idx].mn;
22 int mx = (lx+rx)>>1,my = (ly+ry)>>1,t=1E9;
23 if (Lx<=mx && Ly<=my) t = min(t,queryMN(idx*4+1,lx,mx,ly,my,Lx,Rx,Ly,Ry));
24 if (Lx<=mx && Ry>my) t = min(t,queryMN(idx*4+2,lx,mx,my+1,ry,Lx,Rx,Ly,Ry));
25 if (Rx>mx && Ly<=my) t = min (t,queryMN(idx*4+3,mx+1,rx,ly,my,Lx,Rx,Ly,Ry));
26 if (Rx>mx&&Ry>my) t = min (t,queryMN(idx*4+4,mx+1,rx,my+1,ry,Lx,Rx,Ly,Ry));
27 return t;
28}
29int queryMX( int idx,int lx,int rx,int ly,int ry,int Lx,int Rx,int Ly,int Ry)
30{
31 if (Lx<=lx && Rx>=rx && Ly<=ly && Ry>=ry) return tree[idx].mx;
32 int mx = (lx+rx)>>1,my = (ly+ry)>>1,t=0;
33 if (Lx<=mx && Ly<=my) t = max(t,queryMX(idx*4+1,lx,mx,ly,my,Lx,Rx,Ly,Ry));
34 if (Lx<=mx && Ry>my) t = max(t,queryMX(idx*4+2,lx,mx,my+1,ry,Lx,Rx,Ly,Ry));
35 if (Rx>mx && Ly<=my) t = max (t,queryMX(idx*4+3,mx+1,rx,ly,my,Lx,Rx,Ly,Ry));
36 if (Rx>mx&&Ry>my) t = max(t,queryMX(idx*4+4,mx+1,rx,my+1,ry,Lx,Rx,Ly,Ry));
37 return t;
38}
39void init()
40{
41 for ( int i = 0 ; i < 8E6 ; i++) tree[i].init();
42}
43int main(){
44#ifdef YourCodeHasBug
45// freopen("in2","r",stdin);
46#endif
47 int T;
48 cin>>T;
49 int cas = 0 ;
50 while (T--)
51 {
52 init();
53 scanf("%d",&n);
54 for ( int i = 1 ; i <= n ; i++)
55 for ( int j = 1 ; j <= n ; j++)
56 {
57 scanf("%d",&a[i][j]);
58// cout<<"a[i][j]:"<<a[i][j]<<endl;
59 insert(0,1,n,1,n,i,j,a[i][j]);
60 }
61// for ( int i = 0 ; i <= 20 ; i++) printf("tree_mn:%d mx:%d\n",tree[i].mn,tree[i].mx);
62 int m;
63 scanf("%d",&m);
64 printf("Case #%d:\n",++cas);
65 while (m--)
66 {
67 int x,y,L;
68 scanf("%d %d %d",&x,&y,&L);
69 int Lx = max(x-L/2,1);
70 int Rx = min(n,x+L/2);
71 int Ly = max(y-L/2,1);
72 int Ry = min(n,y+L/2);
73// printf("x:[%d,%d] y:[%d,%d]\n",Lx,Rx,Ly,Ry);
74 int mn = queryMN(0,1,n,1,n,Lx,Rx,Ly,Ry);
75 int mx = queryMX(0,1,n,1,n,Lx,Rx,Ly,Ry);
76 int newval = floor((mn+mx)/2);
77 //printf("mn:%d mx:%d %d\n",mn,mx,newval);
78 printf("%d\n",newval);
79 insert(0,1,n,1,n,x,y,newval);
80 }
81 }
82#ifdef YourCodeHasBug
83 fclose(stdin);
84#endif
85 return 0;
86}
然后又写了一个二维线段树的版本，借鉴了kuangbin的写法，改成了自己习惯的代码风格。
果然常数差好多。。。(据说是因为四叉树退化得厉害QAQ
第三个是四叉树的做法，第二个是kuangbin 的 树套树版本的二维线段树
第一个是我改写kuangbin代码之后的代码。
可以看出，四叉树虽然好写好理解一点，但是时间上不太优秀啊....
/* ***********************************************
Author :111qqz
Created Time :2017年11月10日 星期五 17时18分40秒
File Name :4819_2D.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=803;
7struct Treey
8{
9 int l,r;
10 int Max,Min;
11};
12int n;
13int rtx[N],rty[N] ; //rtx[i]表示横坐标为i的点属于哪棵线段树
14struct Treex
15{
16 int l,r;
17 Treey treey[N<<2];
18 void build ( int _l,int _r,int rt)
19 {
20 treey[rt].l = _l;
21 treey[rt].r = _r;
22 treey[rt].Max = -inf;
23 treey[rt].Min = inf;
24 if (_l==_r)
25 {
26 rty[_l] = rt;
27 return;
28 }
29 int m = (_l + _r) / 2;
30 build (_l,m,rt<<1);
31 build(m+1,_r,rt<<1|1);
32 }
33 int QMin( int L,int R,int rt)
34 {
35 if (treey[rt].l >= L && treey[rt].r <= R) return treey[rt].Min;
36 int m = (treey[rt].l + treey[rt].r) / 2;
37 int ret = 1E9;
38 if (L<=m) ret = QMin(L,R,rt<<1);
39 if (R>=m+1) ret = min(ret,QMin(L,R,rt<<1|1));
40 return ret;
41 }
42 int QMax( int L,int R,int rt)
43 {
44 if (treey[rt].l >= L && treey[rt].r <= R) return treey[rt].Max;
45 int m = (treey[rt].l + treey[rt].r) / 2;
46 int ret = 0 ;
47 if (L<=m) ret = QMax (L,R,rt<<1);
48 if (R>=m+1) ret = max(ret,QMax(L,R,rt<<1|1));
49 return ret;
50 }
51}treex[N<<2];
1void build (int l,int r,int rt)
2{
3 treex[rt].l = l;
4 treex[rt].r = r;
5 treex[rt].build(1,n,1);
6 if (l==r)
7 {
8 rtx[l] = rt;
9 return;
10 }
11 int m = (l+r)>>1;
12 build (lson);
13 build (rson);
14}
15void update ( int x,int y,int val) //单点更新，更新a[x,y]到val
16{
17 int rx = rtx[x];
18 int ry = rty[y];
19 treex[rx].treey[ry].Min = treex[rx].treey[ry].Max = val;
20 for ( int i = rx ; i ; i >>=1)
21 for ( int j = ry ; j ; j >>=1)
22 {
23 if (i==rx && j==ry) continue; //上面更新过了
24 if (j==ry)
25 {
26 treex[i].treey[j].Min = min(treex[i<<1].treey[j].Min,treex[i<<1|1].treey[j].Min);
27 treex[i].treey[j].Max = max(treex[i<<1].treey[j].Max,treex[i<<1|1].treey[j].Max);
28 }
29 else
30 {
31 treex[i].treey[j].Min = min(treex[i].treey[j<<1].Min,treex[i].treey[j<<1|1].Min);
32 treex[i].treey[j].Max = max(treex[i].treey[j<<1].Max,treex[i].treey[j<<1|1].Max);
33 }
34 }
35}
36int QMin( int L1,int R1,int L2,int R2,int rt)
37{
38 if (treex[rt].l >= L1 && treex[rt].r <= R1) return treex[rt].QMin(L2,R2,1);
39 int m = (treex[rt].l + treex[rt].r)/2;
40 int ret = 1E9;
41 if (L1<=m) ret = QMin(L1,R1,L2,R2,rt<<1);
42 if (R1>=m+1) ret = min(ret,QMin(L1,R1,L2,R2,rt<<1|1));
43 return ret;
44}
45int QMax ( int L1,int R1,int L2,int R2,int rt)
46{
47 // printf("rt:%d l:%d r:%d L1:%d R1:%d \n",rt,treex[rt].l,treex[rt].r,L1,R1);
48 if (treex[rt].l >= L1 && treex[rt].r <=R1) return treex[rt].QMax(L2,R2,1);
49 int m = (treex[rt].l + treex[rt].r) / 2;
50 int ret = 0 ;
51 if (L1<=m) ret = QMax(L1,R1,L2,R2,rt<<1);
52 if (R1>=m+1) ret = max(ret, QMax(L1,R1,L2,R2,rt<<1|1));
53 return ret;
54}
1int main()
2{
3#ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5#endif
6 int T,cas=0;
7 cin>>T;
8 while (T--)
9 {
10 printf("Case #%d:\n",++cas);
11 scanf("%d",&n);
12 build (1,n,1);
13 for ( int i = 1 ; i <= n ; i++)
14 for ( int j = 1; j <= n ; j++)
15 {
16 int x;
17 scanf("%d",&x);
18 update(i,j,x);
19 }
20 int q;
21 scanf("%d",&q);
22 while (q--)
23 {
24 int x,y,L;
25 scanf("%d %d %d",&x,&y,&L);
26 int L1 = max(x-L/2,1);
27 int R1 = min(x+L/2,n);
28 int L2 = max(y-L/2,1);
29 int R2 = min(y+L/2,n);
30// printf("[%d,%d] [%d,%d]\n",L1,R1,L2,R2);
31 int Mx = QMax(L1,R1,L2,R2,1);
32 int Mn = QMin(L1,R1,L2,R2,1);
33 int val = floor((Mx+Mn)/2);
34 printf("%d\n",val);
35 update(x,y,val);
36 }
37 }
38#ifndef ONLINE_JUDGE
39 fclose(stdin);
40#endif
41 return 0;
42}