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}
45
46
47void insert( int idx,int lx,int rx,int ly,int ry,int X,int Y,int val)
48{
49// cout<<"val:"<<val<<endl;
50 if (lx==rx&&ly==ry)
51 {
52 tree[idx].mn = tree[idx].mx = val;
53// cout<<"fuck"<<" val:"<<val<<" mn:"<<tree[idx].mn <<" mx:"<<tree[idx];
54 return;
55 }
56 int mx = (lx+rx) >> 1;
57 int my = (ly+ry) >> 1;
58 if (X<=mx&&Y<=my) insert(idx*4+1,lx,mx,ly,my,X,Y,val);
59 if (X<=mx&&Y>=my+1) insert(idx*4+2,lx,mx,my+1,ry,X,Y,val);
60 if (X>=mx+1&&Y<=my) insert(idx*4+3,mx+1,rx,ly,my,X,Y,val);
61 if (X>=mx+1&&Y>=my+1) insert(idx*4+4,mx+1,rx,my+1,ry,X,Y,val);
62// puts("miao");
63 PushUp(idx);
64}
65int queryMN( int idx,int lx,int rx,int ly,int ry,int Lx,int Rx,int Ly,int Ry)
66{
67 if (Lx<=lx && Rx>=rx && Ly<=ly && Ry>=ry) return tree[idx].mn;
68 int mx = (lx+rx)>>1,my = (ly+ry)>>1,t=1E9;
69 if (Lx<=mx && Ly<=my) t = min(t,queryMN(idx*4+1,lx,mx,ly,my,Lx,Rx,Ly,Ry));
70 if (Lx<=mx && Ry>my) t = min(t,queryMN(idx*4+2,lx,mx,my+1,ry,Lx,Rx,Ly,Ry));
71 if (Rx>mx && Ly<=my) t = min (t,queryMN(idx*4+3,mx+1,rx,ly,my,Lx,Rx,Ly,Ry));
72 if (Rx>mx&&Ry>my) t = min (t,queryMN(idx*4+4,mx+1,rx,my+1,ry,Lx,Rx,Ly,Ry));
73 return t;
74}
75int queryMX( int idx,int lx,int rx,int ly,int ry,int Lx,int Rx,int Ly,int Ry)
76{
77 if (Lx<=lx && Rx>=rx && Ly<=ly && Ry>=ry) return tree[idx].mx;
78 int mx = (lx+rx)>>1,my = (ly+ry)>>1,t=0;
79 if (Lx<=mx && Ly<=my) t = max(t,queryMX(idx*4+1,lx,mx,ly,my,Lx,Rx,Ly,Ry));
80 if (Lx<=mx && Ry>my) t = max(t,queryMX(idx*4+2,lx,mx,my+1,ry,Lx,Rx,Ly,Ry));
81 if (Rx>mx && Ly<=my) t = max (t,queryMX(idx*4+3,mx+1,rx,ly,my,Lx,Rx,Ly,Ry));
82 if (Rx>mx&&Ry>my) t = max(t,queryMX(idx*4+4,mx+1,rx,my+1,ry,Lx,Rx,Ly,Ry));
83 return t;
84}
85void init()
86{
87 for ( int i = 0 ; i < 8E6 ; i++) tree[i].init();
88}
89int main(){
90#ifdef YourCodeHasBug
91// freopen("in2","r",stdin);
92#endif
93 int T;
94 cin>>T;
95 int cas = 0 ;
96 while (T--)
97 {
98 init();
99 scanf("%d",&n);
100 for ( int i = 1 ; i <= n ; i++)
101 for ( int j = 1 ; j <= n ; j++)
102 {
103 scanf("%d",&a[i][j]);
104// cout<<"a[i][j]:"<<a[i][j]<<endl;
105 insert(0,1,n,1,n,i,j,a[i][j]);
106 }
107// for ( int i = 0 ; i <= 20 ; i++) printf("tree_mn:%d mx:%d\n",tree[i].mn,tree[i].mx);
108 int m;
109 scanf("%d",&m);
110 printf("Case #%d:\n",++cas);
111 while (m--)
112 {
113 int x,y,L;
114 scanf("%d %d %d",&x,&y,&L);
115 int Lx = max(x-L/2,1);
116 int Rx = min(n,x+L/2);
117 int Ly = max(y-L/2,1);
118 int Ry = min(n,y+L/2);
119// printf("x:[%d,%d] y:[%d,%d]\n",Lx,Rx,Ly,Ry);
120 int mn = queryMN(0,1,n,1,n,Lx,Rx,Ly,Ry);
121 int mx = queryMX(0,1,n,1,n,Lx,Rx,Ly,Ry);
122 int newval = floor((mn+mx)/2);
123 //printf("mn:%d mx:%d %d\n",mn,mx,newval);
124 printf("%d\n",newval);
125 insert(0,1,n,1,n,x,y,newval);
126 }
127 }
128#ifdef YourCodeHasBug
129 fclose(stdin);
130#endif
131 return 0;
132}
然后又写了一个二维线段树的版本，借鉴了kuangbin的写法，改成了自己习惯的代码风格。
果然常数差好多。。。(据说是因为四叉树退化得厉害QAQ
第三个是四叉树的做法，第二个是kuangbin 的 树套树版本的二维线段树
第一个是我改写kuangbin代码之后的代码。
可以看出，四叉树虽然好写好理解一点，但是时间上不太优秀啊….
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月10日 星期五 17时18分40秒
4File Name :4819_2D.cpp
5 ************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N=803;
24struct Treey
25{
26 int l,r;
27 int Max,Min;
28};
29int n;
30int rtx[N],rty[N] ; //rtx[i]表示横坐标为i的点属于哪棵线段树
31struct Treex
32{
33 int l,r;
34 Treey treey[N<<2];
35 void build ( int _l,int _r,int rt)
36 {
37 treey[rt].l = _l;
38 treey[rt].r = _r;
39 treey[rt].Max = -inf;
40 treey[rt].Min = inf;
41 if (_l==_r)
42 {
43 rty[_l] = rt;
44 return;
45 }
46 int m = (_l + _r) / 2;
47 build (_l,m,rt<<1);
48 build(m+1,_r,rt<<1|1);
49 }
50 int QMin( int L,int R,int rt)
51 {
52 if (treey[rt].l >= L && treey[rt].r <= R) return treey[rt].Min;
53 int m = (treey[rt].l + treey[rt].r) / 2;
54 int ret = 1E9;
55 if (L<=m) ret = QMin(L,R,rt<<1);
56 if (R>=m+1) ret = min(ret,QMin(L,R,rt<<1|1));
57 return ret;
58 }
59 int QMax( int L,int R,int rt)
60 {
61 if (treey[rt].l >= L && treey[rt].r <= R) return treey[rt].Max;
62 int m = (treey[rt].l + treey[rt].r) / 2;
63 int ret = 0 ;
64 if (L<=m) ret = QMax (L,R,rt<<1);
65 if (R>=m+1) ret = max(ret,QMax(L,R,rt<<1|1));
66 return ret;
67 }
68}treex[N<<2];
69
70void build (int l,int r,int rt)
71{
72 treex[rt].l = l;
73 treex[rt].r = r;
74 treex[rt].build(1,n,1);
75 if (l==r)
76 {
77 rtx[l] = rt;
78 return;
79 }
80 int m = (l+r)>>1;
81 build (lson);
82 build (rson);
83}
84void update ( int x,int y,int val) //单点更新，更新a[x,y]到val
85{
86 int rx = rtx[x];
87 int ry = rty[y];
88 treex[rx].treey[ry].Min = treex[rx].treey[ry].Max = val;
89 for ( int i = rx ; i ; i >>=1)
90 for ( int j = ry ; j ; j >>=1)
91 {
92 if (i==rx && j==ry) continue; //上面更新过了
93 if (j==ry)
94 {
95 treex[i].treey[j].Min = min(treex[i<<1].treey[j].Min,treex[i<<1|1].treey[j].Min);
96 treex[i].treey[j].Max = max(treex[i<<1].treey[j].Max,treex[i<<1|1].treey[j].Max);
97 }
98 else
99 {
100 treex[i].treey[j].Min = min(treex[i].treey[j<<1].Min,treex[i].treey[j<<1|1].Min);
101 treex[i].treey[j].Max = max(treex[i].treey[j<<1].Max,treex[i].treey[j<<1|1].Max);
102 }
103 }
104}
105int QMin( int L1,int R1,int L2,int R2,int rt)
106{
107 if (treex[rt].l >= L1 && treex[rt].r <= R1) return treex[rt].QMin(L2,R2,1);
108 int m = (treex[rt].l + treex[rt].r)/2;
109 int ret = 1E9;
110 if (L1<=m) ret = QMin(L1,R1,L2,R2,rt<<1);
111 if (R1>=m+1) ret = min(ret,QMin(L1,R1,L2,R2,rt<<1|1));
112 return ret;
113}
114int QMax ( int L1,int R1,int L2,int R2,int rt)
115{
116 // printf("rt:%d l:%d r:%d L1:%d R1:%d \n",rt,treex[rt].l,treex[rt].r,L1,R1);
117 if (treex[rt].l >= L1 && treex[rt].r <=R1) return treex[rt].QMax(L2,R2,1);
118 int m = (treex[rt].l + treex[rt].r) / 2;
119 int ret = 0 ;
120 if (L1<=m) ret = QMax(L1,R1,L2,R2,rt<<1);
121 if (R1>=m+1) ret = max(ret, QMax(L1,R1,L2,R2,rt<<1|1));
122 return ret;
123}
124
125int main()
126{
127#ifndef ONLINE_JUDGE
128 freopen("./in.txt","r",stdin);
129#endif
130 int T,cas=0;
131 cin>>T;
132 while (T--)
133 {
134 printf("Case #%d:\n",++cas);
135 scanf("%d",&n);
136 build (1,n,1);
137 for ( int i = 1 ; i <= n ; i++)
138 for ( int j = 1; j <= n ; j++)
139 {
140 int x;
141 scanf("%d",&x);
142 update(i,j,x);
143 }
144 int q;
145 scanf("%d",&q);
146 while (q--)
147 {
148 int x,y,L;
149 scanf("%d %d %d",&x,&y,&L);
150 int L1 = max(x-L/2,1);
151 int R1 = min(x+L/2,n);
152 int L2 = max(y-L/2,1);
153 int R2 = min(y+L/2,n);
154// printf("[%d,%d] [%d,%d]\n",L1,R1,L2,R2);
155 int Mx = QMax(L1,R1,L2,R2,1);
156 int Mn = QMin(L1,R1,L2,R2,1);
157 int val = floor((Mx+Mn)/2);
158 printf("%d\n",val);
159 update(x,y,val);
160 }
161 }
162#ifndef ONLINE_JUDGE
163 fclose(stdin);
164#endif
165 return 0;
166}