(未完待续)
题目链接:Vijos P1512/LibreOJ 10118/LibreOJ 133/信息学奥赛一本通 T1540。
题目
题目描述
这是一道模板题。
给出一个 $n\times m$ 的零矩阵 $A$,你需要完成如下操作:
- $\texttt{1 x y k}$:表示元素 $A _ {x,y}$ 自增 $k$;
- $\texttt{2 a b c d}$:表示询问左上角为 $(a,b)$,右下角为 $(c,d)$ 的子矩阵内所有数的和。
数据范围
对于全部数据,$1\leq n,m\leq 2^{12},1\leq x,a,c\leq n,1\leq y,b,d\leq m,|k|\leq 10^5$,保证操作数目不超过 $3\times 10^5$,且询问的子矩阵存在。
题解
思路
这是二维树状数组的模板题,照做就行。
代码
代码也没什么好说的,写模板就可以了。
#include<cstdio>
typedef long long ll;
//以上为头文件
const int MAXN=(1<<12)+5;
const int MAXM=(1<<12)+5;
struct TreeArray_2{//二维树状数组模板
#define lowbit(x) ( (x) & ( - (x) ) ) //宏定义lowbit(x)
int n,m;//树状数组的行和列
ll unit[MAXN][MAXM];//储存数据的数组
void Update(int x,int y,ll val){//更新函数
register int i,j;
i=x;
while(i<=n){
j=y;
while(j<=m){
unit[i][j]+=val;
j+=lowbit(j);
}
i+=lowbit(i);
}
return;
}
ll Query(int x,int y){//查询函数
register int i,j;
register ll sum=0;
i=x;
while(i){
j=y;
while(j){
sum+=unit[i][j];
j-=lowbit(j);
}
i-=lowbit(i);
}
return sum;
}
#undef lowbit //取消对lowbit(x)的宏定义
};
int n,m,opt;
TreeArray_2 T;
int main(void){
scanf("%d%d",&n,&m);
T.n=n,T.m=m;//确定树状数组大小
while(scanf("%d",&opt)!=EOF){//多次操作,直到文件末尾
if(opt==1){
static int x,y,k;
scanf("%d%d%d",&x,&y,&k);
T.Update(x,y,k);
}
if(opt==2){
static int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%lld\n",T.Query(c,d)-T.Query(a-1,d)-T.Query(c,b-1)+T.Query(a-1,b-1));//注意细节
}
}
return 0;
}
近期评论