【BZOJ 3132】上帝造题的七分钟 / 题解

BZOJ原题地址

洛谷原题地址

题面

写一个支持区间修改区间查询的二维数据结构。

请尝试自行推导公式。先放代码.

代码

#include 
#define maxn 6000
using namespace std;
int n,m;
struct Bit{
    int c[maxn][maxn];
    int lb(int x){
        return (x&-x);
    }
    void add(int x,int y,int z){
        for (int i=x;i<=n;i+=lb(i))
        for (int j=y;j<=m;j+=lb(j))
        c[i][j]+=z;
    }
    int qry(int x,int y){
        int r=0;
        for (int i=x;i;i-=lb(i))
        for (int j=y;j;j-=lb(j))
        r+=c[i][j];
        return r; 
    }
}A,B,C,D;
void Add(int x,int y,int z){
    A.add(x,y,z),B.add(x,y,z*x),C.add(x,y,z*y),D.add(x,y,z*x*y);
}
int Qry(int x,int y){
    return A.qry(x,y)*(x+1)*(y+1)-B.qry(x,y)*(y+1)-C.qry(x,y)*(x+1)+D.qry(x,y);
}
int main(){
    ios::sync_with_stdio(false);
    string X;cin>>X>>n>>m;
    int a,b,x,y,T;
    while(cin>>X){
        cin>>a>>b>>x>>y;
        if (X=="L"){
            cin>>T;x++,y++;
            Add(a,b,T),Add(x,y,T),Add(x,b,-T),Add(a,y,-T);
        }
        else{
            a--,b--;
            cout<