noj 1004 用树状数组做多维区间求和 .txt

ACM资料大集合

//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;
}