LibreOJ--133--2 Dツリー配列--単点修正+平面クエリー
1534 ワード
これはテンプレートの問題です.
nを与える×mのゼロマトリクスAAは、以下の操作を完了する必要があります.
Input
入力された最初の行には2つの正の整数n,mがある.次の行は、ファイルが終了するまで1行ずつ操作します.
Output
考え方:2 Dツリー配列--単点修正+区間クエリーで、1 Dツリー配列を改善するだけでいい.
参考:POJ 1195:https://blog.csdn.net/queque_heiya/article/details/105895060
注意:LibreOJのテーマの出力量は大きく、できるだけread()とlongでintを使わないことができます.
nを与える×mのゼロマトリクスAAは、以下の操作を完了する必要があります.
1 x y k:元素Axを表し、yはkから増加する.2 a b c d:質問左上角が(a,b)、右下角が(c,d)のサブマトリクス内のすべての数の和を表す.Input
入力された最初の行には2つの正の整数n,mがある.次の行は、ファイルが終了するまで1行ずつ操作します.
Output
2操作毎に、この操作に対する回答を表す整数が出力される.
2 2
1 1 1 3
1 2 2 4
2 1 1 2 2
7
Hint考え方:2 Dツリー配列--単点修正+区間クエリーで、1 Dツリー配列を改善するだけでいい.
参考:POJ 1195:https://blog.csdn.net/queque_heiya/article/details/105895060
注意:LibreOJのテーマの出力量は大きく、できるだけread()とlongでintを使わないことができます.
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
const int maxa=1024*4+10;//4096
LL a[maxa][maxa];
LL n,m;
LL lowbit(LL i){
return i&-i;
}
void add(LL x,LL y,LL p){
for(LL i=x;i<=n;i+=lowbit(i))
for(LL j=y;j<=m;j+=lowbit(j))
a[i][j]+=p;
}
LL sum(int x,int y){
LL ans=0;
for(LL i=x;i>0;i-=lowbit(i))
for(LL j=y;j>0;j-=lowbit(j))
ans+=a[i][j];
return ans;
}
int main(){
memset(a,0,sizeof a);
scanf("%lld%lld",&n,&m);
LL op,x,y,k,r,l;
while(scanf("%lld",&op)!=EOF){
if(op==1){
scanf("%lld%lld%lld",&x,&y,&k);
add(x,y,k);
}
if(op==2){
scanf("%lld%lld%lld%lld",&x,&y,&r,&l);
printf("%lld
",sum(r,l)-sum(r,y-1)-sum(x-1,l)+sum(x-1,y-1));
}
}
}