首页 > 代码库 > tyvj P1716 - 上帝造题的七分钟 二维树状数组区间查询及修改 二维线段树

tyvj P1716 - 上帝造题的七分钟 二维树状数组区间查询及修改 二维线段树

2024-07-21 05:06:54   209人阅读

P1716 - 上帝造题的七分钟

From Riatre    Normal (OI)
总时限：50s    内存限制：128MB    代码长度限制：64KB

背景 Background

裸体就意味着身体。

描述 Description

“第一分钟，X说，要有矩阵，于是便有了一个里面写满了0的n×m矩阵。
第二分钟，L说，要能修改，于是便有了将左上角为(a,b)，右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。
第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。
第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。
第五分钟，和雪说，要有耐心，于是便有了时间限制。
第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
——《上帝造裸题的七分钟》
所以这个神圣的任务就交给你了。

输入格式 InputFormat

输入数据的第一行为X n m，代表矩阵大小为n×m。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：
    L a b c d delta —— 代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。
    k a b c d     —— 代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。

请注意，k为小写。

输出格式 OutputFormat

针对每个k操作，在单独的一行输出答案。

样例输入 SampleInput [复制数据]

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

样例输出 SampleOutput [复制数据]

12

数据范围和注释 Hint

对于10%的数据，1 ≤ n ≤ 16, 1 ≤ m ≤ 16, 操作不超过200个.
对于60%的数据，1 ≤ n ≤ 512, 1 ≤ m ≤ 512.
对于100%的数据，1 ≤ n ≤ 2048, 1 ≤ m ≤ 2048, 1 ≤ delta ≤ 500,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。

来源 Source

by XLk
状态
Accepted
题号P1716
类型(?)高级数据结构
通过99人
提交392次
通过率25%
提交评测 我的记录
  • 查看本题解答排行
  • 前往本题讨论区
  • 阅读本题题解
  • 查看本题数据
  • 查看参考代码(VIP)
 
　　热烈庆祝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 - 上帝造题的七分钟 二维树状数组区间查询及修改 二维线段树


联系
我们