?? noj 1004 用樹狀數組做多維區間求和 .txt
字號:
//NOJ 1004 用樹狀數組做多維區間求和
/*
輸入:
100
A 10 10 40 5
A 20 50 40 5
Q 10 10 10 100 100 100
S 30 40 50 34
Q 10 10 10 50 50 50
S 30 40 50 10
Q 10 10 10 50 50 50
Q 10 10 30 10 10 40
0
輸出:
10
-24
-34
5
*/
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <time.h>
using namespace std;
#define NMAX 102
#define MAX 999999
#define PI 3.1415926
int c[NMAX][NMAX][NMAX];
int Lowbit(int k)
{
return k & ( k ^ (k-1) );
}
void Change(int k,int q,int r,int x,int numa,int numb,int numc)
{ //改動c[k][q][r]
int kk,qq,rr;
kk=k;qq=q; rr=r;
while(kk<=numa)
{
qq=q;
while(qq<=numb)
{
rr=r;
while(rr<=numc)
{
c[kk][qq][rr]+=x;
rr+=Lowbit(rr);
}
qq+=Lowbit(qq);
}
kk+=Lowbit(kk);
}
}
int Getsum(int k,int q,int r)
{ //計算從a[1][1][1]到a[k][q][r]的和
int kk,qq,rr,sum=0;
kk=k;qq=q;rr=r;
while(kk>0)
{
qq=q;
while(qq>0)
{
rr=r;
while(rr>0)
{
sum+=c[kk][qq][rr];
rr-=Lowbit(rr);
}
qq-=Lowbit(qq);
}
kk-=Lowbit(kk);
}
return sum;
}
int Solve(int sk,int sq,int sr,int tk,int tq,int tr)
{ //利用容斥原理計算
int up_zuo_sum=0,up_xia_sum=0,up_jiao_sum=0,up_totle_sum=0;
int down_zuo_sum=0,down_xia_sum=0,down_jiao_sum=0,down_totle_sum=0;
int sum=0,up_sum,down_sum;
up_zuo_sum=Getsum(sk,tq,tr);
up_xia_sum=Getsum(tk,sq,tr);
up_jiao_sum=Getsum(sk,sq,tr);
up_totle_sum=Getsum(tk,tq,tr);
down_zuo_sum=Getsum(sk,tq,sr);
down_xia_sum=Getsum(tk,sq,sr);
down_jiao_sum=Getsum(sk,sq,sr);
down_totle_sum=Getsum(tk,tq,sr);
up_sum=up_totle_sum+up_jiao_sum-up_zuo_sum-up_xia_sum;
down_sum=down_totle_sum+down_jiao_sum-down_zuo_sum-down_xia_sum;
sum=up_sum-down_sum;
return sum;
}
int main()
{
int i,numa,numb,sk,sq,sr,j,tk,tq,tr,num,numc;
char q[10];
scanf("%d",&numa);
numc=numb=numa;
scanf("%s",&q);
while(q[0]!='0')
{
if(q[0]=='Q')
{
scanf("%d %d %d %d %d %d",&sk,&sq,&sr,&tk,&tq,&tr);
printf("%d\n",Solve(sk-1,sq-1,sr-1,tk,tq,tr));
}
else if(q[0]=='A')
{
scanf("%d %d %d %d",&sk,&sq,&sr,&num);
Change(sk,sq,sr,num,numa,numb,numc);
}
else
{
scanf("%d %d %d %d",&sk,&sq,&sr,&num);
Change(sk,sq,sr,-num,numa,numb,numc);
}
scanf("%s",&q);
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -