# 某岛

… : "…アッカリ～ン . .. . " .. .
September 3, 2013

## BZOJ 3132. 上帝造题的七分钟

。。考虑询问矩阵的 “前缀和” [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){
}

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){
}

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