bzoj 3132二次元ツリー配列

3132:神が問題を作った7分
Time Limit: 20 Sec  
Memory Limit: 128 MB
Submit: 522  
Solved: 242
[ Submit][ Status][ Discuss]
Description
「最初の分、Xはマトリックスが必要だと言って、そこに0がいっぱい書いてあるnがありました.×mマトリクス.
2分目、Lは、修正できるようにすると、左上角(a,b)、右下角(c,d)の矩形領域内のすべての数字に1つの値を加算する操作があります.
3分目、kは、クエリーできるようにすると、与えられた矩形領域内のすべての数字とを求める操作があったと述べた.
4分目、虹ニャーは二叉木のデータ構造に基づいて、データ範囲があると言った.
5分目、雪に辛抱強く、時間の制限があったと言った.
6分目、ピアノを食べる男は、手間を省くと言って、演算中および最終結果が32ビットの符号付き整数タイプの表示範囲を超えないことを保証する制限があった.
7分目、この問題はやっと完成したが、問題を作った神牛たちは二度とこの問題のプログラムを書きたくない」と話した.
——『神が裸の問題を作った7分』
だからこの神聖な任務はあなたに任せました.
Input
入力データの第1の挙動X n mは、マトリクスサイズnを表す×m.
入力データの2行目からファイルの最後までの行には、次の2つの操作があります.
L a b c d delta--(a,b)、(c,d)を頂点とする矩形領域内のすべての数字にdeltaを加えることを表す.
k a b c dは、(a,b)、(c,d)を頂点とする矩形領域内のすべての数字の和を表す.
 
kは小文字であることに注意してください.
        
Output
k操作ごとに、個別の行に答えを出力します.
Sample Input
X 4 4 L 1 1 3 3 2 L 2 2 4 4 1 k 2 2 3 3
Sample Output
12
HINT
100%のデータに対して、1≦n≦2048、1≦m≦2048、1≦abs(delta)≦500、操作は200000個を超えず、演算中および最終結果が32ビットバンドシンボル整数タイプの表現範囲を超えないことを保証する.
この問題は同様に差分思想を利用することができ、C[i][j]=A[i][j]-A[i-1][j]-A[i][j-1]+A[i-1][j-1]
A[i][j]=sigma[k,1,i][l,1,j](C[k][l])これは数学的帰納法で証明できる
そしてsigma[i,1,n][j,1,m](A[i][j])=sigma[i,1,n][j,1,m][k,1,i][l,1,j](C[k][l])
=sigma[k,1,n][l,1,n](C[k][l]*(n+1-k)*(m+1-l)) 
C[i][j]とi*C[i][j]とj*C[i][j]とi*j*C[i][j]のメンテナンス
矩形(x 1,y 1)->(x 2,y 2)updateには,(x 1,y 1),(x 1,y 2+1),(x 2+1,y 1),(x 2+1,y 2+1)の4点が必要である.
この絵を描くとC[i][j]の意味によってこの4点だけが変化し、0行目と0列目がすべて0であることを保証しなければならない.そうしないとエラーになる.
コード:

#include
#include
#include
#define ll long long
#define Maxn 2049
using namespace std;

char s[2];
int n,m;
ll c[4][Maxn][Maxn];
void U(int id,int x,int y,int d){
    for(int i=x;i<=n;i+=i&-i)
        for(int j=y;j<=m;j+=j&-j)
            c[id][i][j]+=d;
}
ll sum(int id,int x,int y){
    ll res=0;
    for(int i=x;i>0;i-=i&-i)
        for(int j=y;j>0;j-=j&-j)
            res+=c[id][i][j];
    return res;
}
void update(int x1,int y1,int x2,int y2,int d){
    U(0,x1,y1,d);U(0,x1,y2+1,-d); //c[i][j]
    U(0,x2+1,y1,-d);U(0,x2+1,y2+1,d);
    U(1,x1,y1,x1*d);U(1,x1,y2+1,-x1*d); //i*C[i][j]
    U(1,x2+1,y1,-(x2+1)*d);U(1,x2+1,y2+1,(x2+1)*d);
    U(2,x1,y1,y1*d);U(2,x1,y2+1,-(y2+1)*d); //j*C[i][j]
    U(2,x2+1,y1,-y1*d);U(2,x2+1,y2+1,(y2+1)*d);
    U(3,x1,y1,x1*y1*d);U(3,x1,y2+1,-x1*(y2+1)*d); //i*j*C[i][j]
    U(3,x2+1,y1,-(x2+1)*y1*d);U(3,x2+1,y2+1,(x2+1)*(y2+1)*d);
}
ll get(int x,int y){
    return (x+1)*(y+1)*sum(0,x,y)-(y+1)*sum(1,x,y)-(x+1)*sum(2,x,y)+sum(3,x,y);
}
int main()
{
    int x1,y1,x2,y2,k;
    scanf("%*s%d%d",&n,&m);
    while(~scanf("%s",s)){
        if(s[0]=='L'){
            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
            update(x1,y1,x2,y2,k);
        }
        else{
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%d
",get(x2,y2)-get(x1-1,y2)-get(x2,y1-1)+get(x1-1,y1-1));
        }
    }
	return 0;
}