做法类似某题。。这里就不赘述了。。

。。考虑询问矩阵的 “前缀和” [1, 1]-[x, y]。设 $$d_{ij}$$ 是 [i, j] 对右下角的 [i, j]-[n, m] 贡献，则有：

$$! \begin{aligned} Sum &=\sum_{i=1}^{x}\sum_{i=1}^{y} d_{ij}(x-i+1)(y-j+1) \\&= \sum_{i=1}^{x}\sum_{i=1}^{y} d_{ij}(x+1)(y+1) – d_{ij} i (y+1) – d_{ij} j (x+1) + d_{ij} i j \end{aligned}$$

用二维树状数组分别维护这四个增量即可。

const int N = 2049;

int S[N][N], Sx[N][N], Sy[N][N], Sxy[N][N];
int n, m;

void Add(int S[N][N], int x, int _y, int d){
    for (;x<=n;x+=low_bit(x))
        for (int y=_y;y<=m;y+=low_bit(y))
            S[x][y] += d;
}

int Sum(int S[N][N], int x, int _y){
    int z=0; for (;x;x^=low_bit(x))
        for (int y=_y;y;y^=low_bit(y))
            z += S[x][y];
    return z;
}

void Add(int x, int y, int d){
    Add(S, x, y, d), Add(Sx, x, y, x*d), Add(Sy, x, y, y*d), Add(Sxy, x, y, x*y*d);
}

int Sum(int x, int y){
    return Sum(S, x, y)*(x+1)*(y+1) - Sum(Sx, x, y)*(y+1) - Sum(Sy, x, y)*(x+1) + Sum(Sxy, x, y);
}

int Sum(int x0, int y0, int x1, int y1){
    return Sum(x1, y1) - Sum(x1, y0-1) - Sum(x0-1, y1) + Sum(x0-1, y0-1);
}

void Add(int x0, int y0, int x1, int y1, int d){
    Add(x0, y0, d), Add(x0, y1+1, -d), Add(x1+1, y0, -d), Add(x1+1, y1+1, d);
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    scanf("%*c%d%d", &n, &m);

    char cmd; int x0, y0, x1, y1;

    while (~scanf(" %c", &cmd)){
        RD(x0, y0, x1, y1);
        if (cmd == 'L') Add(x0, y0, x1, y1, RDD());
        else OT(Sum(x0, y0, x1, y1));
    }
}

https://gist.github.com/lychees/6422304

Posted by xiaodao
Category: BZOJ