首页 > 代码库 > tyvj P1716 - 上帝造题的七分钟 二维树状数组区间查询及修改 二维线段树
tyvj P1716 - 上帝造题的七分钟 二维树状数组区间查询及修改 二维线段树
热烈庆祝AC200~~
这道题被hja坑去写二维线段树,结果不是TLE就是MLE,正确的做法是二维树状数组区间修改与区间查询,在网上找得到详细解法。
大体思路为维护a[][]使得前缀和sum[x][y]=segma(num[i][j])=segma(a[i][j]*(x-i+1)*(y-j+1))=segma(a[i][j]*(x+1)*(y+1)-(i+j)*a[i][j])
=segma(a[i][j])*(x+1)*(y+1)+segma(i*j*a[i][j])-segma(j*a[i][j])*(x+1)-segma(i*a[i][j])*(y+1)
最后,可以用4个树状数组分别维护上式中segma中引用部分。
下面贴上两种解法代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define MAXN 2050 7 #define MAXT 5000000 8 typedef int tree_t[MAXN][MAXN]; 9 tree_t tree1,tree2,tree3,tree4;10 int lowbit(int x)11 {12 return x&(-x);13 }14 void add_val(tree_t tree,int x,int y,int v)15 {16 // cout<<"ADD"<<x<<" "<<y<<" "<<v<<endl;17 int i,j;18 for (i=x;i<MAXN;i+=lowbit(i))19 {20 for (j=y;j<MAXN;j+=lowbit(j))21 {22 tree[i][j]+=v;23 }24 }25 }26 int query_sum(tree_t tree,int x,int y)27 {28 int i,j;29 int ret=0;30 for (i=x;i;i-=lowbit(i))31 {32 for (j=y;j;j-=lowbit(j))33 {34 ret+=tree[i][j];35 }36 }37 return ret;38 }39 //sum(x,y)=segma(a[i][j]*(x-i+1)*(y-j+1))40 // =segma(a[i][j]*(x+1)*(y+1)-(i+j)*a[i][j]);41 // =segma(a[i][j])*(x+1)*(y+1)-segma((i+j)*a[i][j])42 //43 void add_matrix(int xl,int yl,int xr,int yr,int v)44 {45 add_val(tree1,xr+1,yr+1,v);46 add_val(tree1,xl,yl,v);47 add_val(tree1,xl,yr+1,-v);48 add_val(tree1,xr+1,yl,-v);49 add_val(tree2,xr+1,yr+1,v*(xr+1)*(yr+1));50 add_val(tree2,xl,yl,v*(xl+0)*(yl+0));51 add_val(tree2,xl,yr+1,-v*(xl+0)*(yr+1));52 add_val(tree2,xr+1,yl,-v*(yl+0)*(xr+1));53 54 add_val(tree3,xr+1,yr+1,v*(xr+1));55 add_val(tree3,xl,yl,v*(xl+0));56 add_val(tree3,xl,yr+1,-v*(xl+0));57 add_val(tree3,xr+1,yl,-v*(xr+1));58 59 add_val(tree4,xr+1,yr+1,v*(yr+1));60 add_val(tree4,xl,yl,v*(yl+0));61 add_val(tree4,xl,yr+1,-v*(yr+1));62 add_val(tree4,xr+1,yl,-v*(yl+0));63 64 } 65 int query_matrix(int x,int y)66 {67 if (!x || !y)return 0;68 int ret=0;69 int t;70 ret+=query_sum(tree1,x,y)*(x+1)*(y+1);71 ret-=(t=query_sum(tree3,x,y))*(y+1);72 ret-=query_sum(tree4,x,y)*(x+1);73 ret+=query_sum(tree2,x,y);74 return ret;75 }76 int main()77 {78 freopen("input.txt","r",stdin);79 int i,j,k;80 int n,m;81 int x,y,z;82 char opt;83 scanf("%c%d%d\n",&opt,&n,&m);84 int a,b,c,d,e;85 while (~scanf("%c",&opt))86 {87 if (opt==‘L‘)88 {89 scanf("%d%d%d%d%d\n",&a,&b,&c,&d,&e);90 add_matrix(a,b,c,d,e);91 }else92 {93 scanf("%d%d%d%d\n",&a,&b,&c,&d);94 printf("%d\n",query_matrix(a-1,b-1)+query_matrix(c,d)95 -query_matrix(a-1,d)-query_matrix(c,b-1));96 }97 }98 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define MAXN 2050 7 #define MAXT 2000000 8 #define midx ((tree[now].lx+tree[now].rx)>>1) 9 #define midy ((tree[now].ly+tree[now].ry)>>1) 10 #define tnly tree[now].ly 11 #define tnry tree[now].ry 12 #define tnlx tree[now].lx 13 #define tnrx tree[now].rx 14 #define tnlazy tree[now].lazy 15 #define area(t) ((tree[t].rx-tree[t].lx+1)*(tree[t].ry-tree[t].ly+1)) 16 struct node 17 { 18 int ch[2][2]; 19 int lx,rx,ly,ry; 20 int sum; 21 int lazy=0; 22 }tree[MAXT]; 23 int root=0,topt=0; 24 void new_node(int &now,int lx,int rx,int ly,int ry) 25 { 26 if (lx>rx ||ly>ry)return ; 27 now=++topt; 28 tnlx=lx; 29 tnrx=rx; 30 tnly=ly; 31 tnry=ry; 32 } 33 34 void down(int now) 35 { 36 if (!tree[now].ch[0][0]) 37 new_node(tree[now].ch[0][0],tnlx,midx,tnly,midy); 38 if (!tree[now].ch[0][1] && tnly<tnry) 39 new_node(tree[now].ch[0][1],tnlx,midx,midy+1,tnry); 40 if (!tree[now].ch[1][0] && tnlx<tnrx) 41 new_node(tree[now].ch[1][0],midx+1,tnrx,tnly,midy); 42 if (!tree[now].ch[1][1] && tnly<tnry && tnlx<tnrx) 43 new_node(tree[now].ch[1][1],midx+1,tnrx,midy+1,tnry); 44 if (tnlazy) 45 { 46 tree[tree[now].ch[0][0]].sum+=tnlazy*area(tree[now].ch[0][0]); 47 tree[tree[now].ch[0][0]].lazy+=tnlazy; 48 if (tnlx<tnrx) 49 { 50 tree[tree[now].ch[1][0]].sum+=tnlazy*area(tree[now].ch[1][0]); 51 tree[tree[now].ch[1][0]].lazy+=tnlazy; 52 } 53 if (tnly<tnry) 54 { 55 tree[tree[now].ch[0][1]].sum+=tnlazy*area(tree[now].ch[0][1]); 56 tree[tree[now].ch[0][1]].lazy+=tnlazy; 57 } 58 if (tnlx<tnrx && tnly<tnry) 59 { 60 tree[tree[now].ch[1][1]].sum+=tnlazy*area(tree[now].ch[1][1]); 61 tree[tree[now].ch[1][1]].lazy+=tnlazy; 62 } 63 tnlazy=0; 64 } 65 } 66 void up(int now) 67 { 68 tree[now].sum=0; 69 tree[now].sum+=tree[tree[now].ch[0][0]].sum; 70 tree[now].sum+=tree[tree[now].ch[1][0]].sum; 71 tree[now].sum+=tree[tree[now].ch[0][1]].sum; 72 tree[now].sum+=tree[tree[now].ch[1][1]].sum; 73 } 74 void add_val(int &now,int lx,int rx,int ly,int ry,int v) 75 { 76 if (tnlx==lx &&tnly==ly && tnrx==rx &&tnry==ry) 77 { 78 tree[now].sum+=v*(rx-lx+1)*(ry-ly+1); 79 tree[now].lazy+=v; 80 return ; 81 } 82 down(now); 83 if (rx<=midx && ry<=midy) 84 { 85 add_val(tree[now].ch[0][0],lx,rx,ly,ry,v); 86 up(now); 87 return ; 88 } 89 if (rx<=midx && ly> midy) 90 { 91 add_val(tree[now].ch[0][1],lx,rx,ly,ry,v); 92 up(now); 93 return ; 94 } 95 if (lx> midx && ry<=midy) 96 { 97 add_val(tree[now].ch[1][0],lx,rx,ly,ry,v); 98 up(now); 99 return ;100 }101 if (lx> midx && ly> midy)102 {103 add_val(tree[now].ch[1][1],lx,rx,ly,ry,v);104 up(now);105 return ;106 }107 if (rx<=midx)108 {109 add_val(tree[now].ch[0][0],lx,rx,ly,midy,v);110 add_val(tree[now].ch[0][1],lx,rx,midy+1,ry,v);111 up(now);112 return ;113 }114 if (lx> midx)115 {116 add_val(tree[now].ch[1][0],lx,rx,ly,midy,v);117 add_val(tree[now].ch[1][1],lx,rx,midy+1,ry,v);118 up(now);119 return ;120 }121 if (ry<=midy)122 {123 add_val(tree[now].ch[0][0],lx,midx,ly,ry,v);124 add_val(tree[now].ch[1][0],midx+1,rx,ly,ry,v);125 up(now);126 return ;127 }128 if (ly> midy)129 {130 add_val(tree[now].ch[0][1],lx,midx,ly,ry,v);131 add_val(tree[now].ch[1][1],midx+1,rx,ly,ry,v);132 up(now);133 return ;134 }135 add_val(tree[now].ch[0][0],lx,midx,ly,midy,v);136 add_val(tree[now].ch[0][1],lx,midx,midy+1,ry,v);137 add_val(tree[now].ch[1][0],midx+1,rx,ly,midy,v);138 add_val(tree[now].ch[1][1],midx+1,rx,midy+1,ry,v);139 up(now);140 return ;141 }142 int query(int now,int lx,int rx,int ly,int ry)143 {144 if (tree[now].lx==lx && tree[now].rx==rx &&145 tree[now].ly==ly && tree[now].ry==ry)146 {147 return tree[now].sum;148 } 149 down(now);150 int ans=0;151 if (rx<=midx && ry<=midy)152 {153 ans=query(tree[now].ch[0][0],lx,rx,ly,ry);154 return ans;155 }156 if (rx<=midx && ly> midy)157 {158 ans=query(tree[now].ch[0][1],lx,rx,ly,ry);159 return ans;160 }161 if (lx> midx && ry<=midy)162 {163 ans=query(tree[now].ch[1][0],lx,rx,ly,ry);164 return ans;165 }166 if (lx> midx && ly> midy)167 {168 ans=query(tree[now].ch[1][1],lx,rx,ly,ry);169 return ans;170 }171 if (rx<=midx)172 {173 ans=query(tree[now].ch[0][0],lx,rx,ly,midy);174 ans+=query(tree[now].ch[0][1],lx,rx,midy+1,ry);175 return ans;176 }177 if (lx> midx)178 {179 ans=query(tree[now].ch[1][0],lx,rx,ly,midy);180 ans+=query(tree[now].ch[1][1],lx,rx,midy+1,ry);181 return ans;182 }183 if (ry<=midy)184 {185 ans=query(tree[now].ch[0][0],lx,midx,ly,ry);186 ans+=query(tree[now].ch[1][0],midx+1,rx,ly,ry);187 return ans;188 }189 if (ly> midy)190 {191 ans=query(tree[now].ch[0][1],lx,midx,ly,ry);192 ans+=query(tree[now].ch[1][1],midx+1,rx,ly,ry);193 return ans;194 }195 ans=query(tree[now].ch[0][0],lx,midx,ly,midy);196 ans+=query(tree[now].ch[0][1],lx,midx,midy+1,ry);197 ans+=query(tree[now].ch[1][0],midx+1,rx,ly,midy);198 ans+=query(tree[now].ch[1][1],midx+1,rx,midy+1,ry);199 up(now);200 return ans;201 }202 int main()203 {204 //freopen("input.txt","r",stdin);205 int i,j,k;206 int n,m;207 int x,y,z;208 char opt;209 scanf("%c%d%d\n",&opt,&n,&m);210 tree[1].lx=1;tree[1].rx=n;211 tree[1].ly=1;tree[1].ry=m;212 tree[1].sum=tree[1].lazy=0;213 topt=1;214 root=1;215 int a,b,c,d,e;216 while (~scanf("%s",&opt))217 {218 if (opt==‘L‘)219 {220 scanf("%d%d%d%d%d\n",&a,&b,&c,&d,&e);221 add_val(root,a,c,b,d,e);222 }else223 {224 scanf("%d%d%d%d\n",&a,&b,&c,&d);225 printf("%d\n",query(root,a,c,b,d));226 }227 }228 229 }
tyvj P1716 - 上帝造题的七分钟 二维树状数组区间查询及修改 二维线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。