BZOJ3132/上帝造题的七分钟

Posted on By 二价氢

二维树状数组

因为要区间修改区间和,所以得要四个,差不多就是做类似于前缀和的前缀和那样

题解:http://hi.baidu.com/strongoier/item/13f22104f6b4c50d6c904852

AC-Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=2052;
int n,m;
int B1[MAXN][MAXN],B2[MAXN][MAXN],B3[MAXN][MAXN],B4[MAXN][MAXN];
inline int LowBit(int x)
{
    return x&(-x);
}
void add(int (*s)[MAXN],int x,int y,int d)
{
    for (int i=x;i<=n;i+=LowBit(i))
        for (int j=y;j<=m;j+=LowBit(j))
            s[i][j]+=d;
}
int sum(int (*s)[MAXN],int x,int y)
{
    int ret=0;
    for (int i=x;i>0;i-=LowBit(i))
        for (int j=y;j>0;j-=LowBit(j))
            ret+=s[i][j];
    return ret;
}
void ADD(int x,int y,int d)
{
    if (!x||!y)
        return;
    add(B1,x,y,x*y*d);
    add(B2,x,1,x*d);add(B2,x,y,-x*d);
    add(B3,1,y,y*d);add(B3,x,y,-y*d);
    add(B4,1,1,d);add(B4,x,y,d);add(B4,x,1,-d);add(B4,1,y,-d);
}
int QUERY(int x,int y)
{
    return x&&y?(sum(B1,x,y)+sum(B2,x,y)*y+sum(B3,x,y)*x+sum(B4,x,y)*x*y):0;
}
int main()
{
    char op[20];
    int x1,y1,x2,y2,d;
    scanf("%s%d%d",op,&n,&m);
    while (scanf("%s%d%d%d%d",op,&x1,&y1,&x2,&y2)!=EOF)
    {
        if (op[0]=='L')
        {
            scanf("%d",&d);
            ADD(x2,y2,d);ADD(x1-1,y1-1,d);
            ADD(x2,y1-1,-d);ADD(x1-1,y2,-d);
        }else
        {
            printf("%d\n",QUERY(x2,y2)-QUERY(x2,y1-1)-QUERY(x1-1,y2)+QUERY(x1-1,y1-1));
        }
    }
    return 0;
}