测试2T2

问题 B: 上帝造题的七分钟

“第一分钟，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操作，在单独的一行输出答案。

样例输入

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

样例输出

提示

【数据范围】

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

裸的二维树状数组

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char s[2];
ll a,b,c,d,del,tt,sum,n,m,anss;
ll f[4][2050][2050];
ll lowbit(int x)
{
    return(x&-x);
}
ll ans(int id,int x,int y)
{
    ll sum=0;
    for (int i=x;i;i-=lowbit(i))
        for (int j=y;j;j-=lowbit(j))
            sum+=f[id][i][j];
    return sum;
}
ll ask(int x,int y)
{
   return ((x+1)*(y+1)*ans(0,x,y)-(y+1)*ans(1,x,y)-(x+1)*ans(2,x,y)+ans(3,x,y));    
 } 
void U(int id,int x,int y,int del)
{    
    for (int i=x;i<=n;i+=lowbit(i))
        for (int j=y;j<=m;j+=lowbit(j))
            f[id][i][j]+=del; 
}
void update(int x1,int y1,int x2,int y2,int d){  
    U(0,x1,y1,d);U(0,x1,y2+1,-d); //f[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*f[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*f[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*f[i][j]  
    U(3,x2+1,y1,-(x2+1)*y1*d);U(3,x2+1,y2+1,(x2+1)*(y2+1)*d);  
}  
int main()
{
        scanf("X %lld %lld",&n,&m);
        while(~scanf("%s",s))
        {
            if (s[0]=='L')
            {
               scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&del);
               update(a,b,c,d,del);    
            }
            else 
            {
                scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
                anss=ask(c,d)-ask(c,b-1)-ask(a-1,d)+ask(a-1,b-1);
                printf("%lld
",anss);
            }
        }
}

代码NP提供

用d[i][j]表示a[i][j]到a[n][m]的整体增量

sigma(a[1][1]...a[i][j])=sigma(x:1..i,y:1.j;(i-x+1)*(j-y+1)*d[x][y])

化减右边那个东西，然后得到

(i-x+1)*(j-y+1)*d[x][y]=(i+1)*(j+1)*d[x][y]-(i+1)*(y)*d[x][y]-(x)*(j+1)*d[x][y]+x*y*d[x][y];

仿照一维时的操作，分别为d[x][y],y*d[x][y],x*d[x][y],x*y*d[x][y],求和即可