“第一分钟，X说，要有矩阵，于是便有了一个里面写满了0的n×m矩阵。

第二分钟，L说，要能修改，于是便有了将左上角为(a,b)，右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。

第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。

第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。

第五分钟，和雪说，要有耐心，于是便有了时间限制。

第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”

——《上帝造裸题的七分钟》

所以这个神圣的任务就交给你了。

输入数据的第一行为X n m，代表矩阵大小为n×m。

从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：

　　L a b c d delta —— 代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。

　　k a b c d　　 —— 代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。

请注意，k为小写。

针对每个k操作，在单独的一行输出答案。

对于100%的数据，1 ≤ n ≤ 2048, 1 ≤ m ≤ 2048, 1 ≤ delta ≤ 500,操作不超过200000个,保证运算过程中及最终结果均不超过32位带符号整数类型的表示范围。

tyvj

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

#define MAXN (2050)

int lowbit(int x){return x&(-x);}

int n,m,x1,x2,y1,y2,delta;

struct arr_tree

{

    int b[MAXN][MAXN];

    arr_tree(){memset(b,,sizeof(b));   }

    void add(int x,int y,int c,bool b1,bool b2)

    {

        if (!x||!y||x>n||y>m) return;

        if (b1) c*=(x-);if (b2) c*=(y-);if (!c) return;

        for (int i=x;i<=n;i+=lowbit(i))

            for (int j=y;j<=m;j+=lowbit(j)) b[i][j]+=c;

    }

    int qur(int x,int y)

    {

        if (!x||!y) return ;

        int ans=;

        for (int i=x;i;i-=lowbit(i))

            for (int j=y;j;j-=lowbit(j)) ans+=b[i][j];

        return ans;

    }

    void add(int x1,int y1,int x2,int y2,int c,bool b1,bool b2)

    {

        add(x2+,y2+,delta,b1,b2),add(x1,y1,delta,b1,b2);

        add(x1,y2+,-delta,b1,b2),add(x2+,y1,-delta,b1,b2);

    }

}d,di,dj,dij;

int Dsum(int x,int y)

{

    return d.qur(x,y)*x*y+dij.qur(x,y)-di.qur(x,y)*y-dj.qur(x,y)*x;

}

int main()

{

    scanf("X %d %d",&n,&m);

    char c;

    while (scanf("%c",&c)==)

    {

        while (c^'L'&&c^'k') if (scanf("%c",&c)!=) return ;

        switch(c)

        {

            case 'L':

                scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta);

                if (x1>x2) swap(x1,x2),swap(y1,y2);

                d.add(x1,y1,x2,y2,delta,,),di.add(x1,y1,x2,y2,-delta,,);

                dj.add(x1,y1,x2,y2,-delta,,),dij.add(x1,y1,x2,y2,delta,,);

                break;

            default:

                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

                if (x1>x2) swap(x1,x2),swap(y1,y2);

                printf("%d\n",Dsum(x2,y2)+Dsum(x1-,y1-)-Dsum(x1-,y2)-Dsum(x2,y1-));

        }

    }

}