首页 > 代码库 > POJ1195-数据结构嵌套(二维线段树)
POJ1195-数据结构嵌套(二维线段树)
第一次写传说中的数据结构套数据结构,果然坑了一晚上,不过回头想想也没什么难的。二维线段树是一颗基于X轴的线段树,每颗该线段树的节点又是一颗基于Y轴的线段树。X轴线段树的某个节点所表示的Y轴线段树 维护的是该X轴线段树的两个儿子所表示的Y轴线段树维护的数据之和,如果X轴线段树的这个节点没有儿子,则其表示的Y轴线段树 维护的 就是 所有横坐标为X的数据,巨绕。。
下面是POJ1195标程:
P。S。该题内存限制64M,一开始全用的int,一个int 4字节,大概2100*2100*5个int,1024字节=1Kb,算了算86000Kb,大约86M,超了内存,于是只好把部分数据类型改成short int,一个short int 2字节,还是可以的,最后程序大约总共用了50M左右内存。
1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 typedef short int Sint; 7 int len,sum; 8 struct tree_node{ 9 Sint l,r,ls,rs; 10 int s; 11 }; 12 struct seg_tree{ 13 Sint l,r,ls,rs; 14 tree_node tree_y[2100]; 15 Sint sum; 16 }tree_x[2100]; 17 void BuildTree_2(Sint v1,Sint v2,Sint Y_l,Sint Y_r){ 18 tree_node &t=tree_x[v1].tree_y[v2]; 19 t.l=Y_l,t.r=Y_r; 20 if(t.l==t.r){ 21 t.s=0; 22 return; 23 } 24 else{ 25 Sint mid=(t.l+t.r)/2; 26 t.ls=++tree_x[v1].sum;t.rs=++tree_x[v1].sum; 27 BuildTree_2(v1,t.ls,t.l,mid);BuildTree_2(v1,t.rs,mid+1,t.r); 28 t.s=tree_x[v1].tree_y[t.ls].s + tree_x[v1].tree_y[t.rs].s; 29 return; 30 } 31 } 32 void BuildTree_1(Sint X_v,Sint X_l,Sint X_r){ 33 tree_x[X_v].l=X_l,tree_x[X_v].r=X_r; 34 if(X_l==X_r){ 35 BuildTree_2(X_v,0,0,len-1); 36 return; 37 } 38 Sint mid=(X_l+X_r)/2; 39 tree_x[X_v].ls=++sum,tree_x[X_v].rs=++sum; 40 BuildTree_1(tree_x[X_v].ls,X_l,mid); 41 BuildTree_1(tree_x[X_v].rs,mid+1,X_r); 42 43 tree_x[X_v].sum=tree_x[tree_x[X_v].ls].sum; 44 for(int i=0;i<=tree_x[tree_x[X_v].ls].sum;i++){ 45 tree_x[X_v].tree_y[i] = tree_x[tree_x[X_v].ls].tree_y[i]; 46 tree_x[X_v].tree_y[i].s = tree_x[tree_x[X_v].ls].tree_y[i].s + tree_x[tree_x[X_v].rs].tree_y[i].s; 47 } 48 return; 49 } 50 51 void add_2(Sint v1,Sint v2,Sint y,int a){ 52 tree_node &t=tree_x[v1].tree_y[v2]; 53 t.s+=a; 54 if(t.l==t.r) return; 55 Sint mid=(t.l+t.r)/2; 56 if(y<=mid){ 57 add_2(v1,t.ls,y,a); 58 } 59 else{ 60 add_2(v1,t.rs,y,a); 61 } 62 } 63 void add_1(Sint v1,Sint x,Sint y,int a){ 64 add_2(v1,0,y,a); 65 if(tree_x[v1].l==tree_x[v1].r) return; 66 Sint mid=(tree_x[v1].l+tree_x[v1].r)/2; 67 if(x<=mid){ 68 add_1(tree_x[v1].ls,x,y,a); 69 } 70 else{ 71 add_1(tree_x[v1].rs,x,y,a); 72 } 73 return; 74 } 75 76 int query_2(Sint v1,Sint v2,Sint Y_l,Sint Y_r){ 77 tree_node o=tree_x[v1].tree_y[v2]; 78 if(o.r<Y_l || o.l>Y_r) return 0; 79 if(Y_l<=o.l && o.r<=Y_r) return o.s; 80 return query_2(v1,o.ls,Y_l,Y_r) + query_2(v1,o.rs,Y_l,Y_r); 81 } 82 int query_1(Sint v1,Sint X_l,Sint X_r,Sint Y_l,Sint Y_r){ 83 if(tree_x[v1].r<X_l || tree_x[v1].l>X_r) return 0; 84 if(X_l<=tree_x[v1].l && tree_x[v1].r<=X_r) return query_2(v1,0,Y_l,Y_r); 85 return query_1(tree_x[v1].ls,X_l,X_r,Y_l,Y_r) + query_1(tree_x[v1].rs,X_l,X_r,Y_l,Y_r); 86 } 87 88 int main(){ 89 Sint opt,x,y,a,l,b,r,t; 90 while(1){ 91 scanf("%d",&opt); 92 if(opt==0){ 93 scanf("%d",&len); 94 for(int i=0;i<=sum;i++) tree_x[i].sum=0; 95 sum=0; 96 BuildTree_1(0,0,len-1); 97 } 98 if(opt==3) break; 99 if(opt==1){ 100 scanf("%d%d%d",&x,&y,&a); 101 add_1(0,x,y,a); 102 } 103 if(opt==2){ 104 scanf("%d%d%d%d",&l,&b,&r,&t); 105 printf("%d\n",query_1(0,l,r,b,t)); 106 } 107 } 108 return 0; 109 }
POJ1195-数据结构嵌套(二维线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。