省流：二维树状数组
题目传送门
对于一个二维前缀和：
\[\sum_{i=1}^{x} \sum_{j=1}^{y} \sum_{u=1}^{i} \sum_{v=1}^{j} c[u][v]
\]
但是后面两个 \(\sum\) 其实可以变成
\[\sum_{i=1}^{x} \sum_{j=1}^{y} (x-i+1)(y-j+1)c[i][j]
\]
展开
\[\sum_{i=1}^{x} \sum_{j=1}^{y} c[i][j] \cdot (xy-xj+x-iy+ij-i+y-j+1)
\]
小小分解：
\[\sum_{i=1}^{x} \sum_{j=1}^{y} c[i][j] \cdot [(x+1)(y+1)-i(y+1)-j(x+1)+ij]
\]
维护 \(c[i][j],c[i][j] \cdot i,c[i][j] \cdot j,c[i][j] \cdot i \cdot j\) 即可。
code
#include <bits/stdc++.h>
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 998244353;
constexpr int maxk = 2050;int n, m, a, b, c, d, delta;char ch;int t1[maxk][maxk], t2[maxk][maxk], t3[maxk][maxk], t4[maxk][maxk];char cc[2];int lowbit(int x){return x & (-x);
}void update(int x, int y, int d){for (int i = x; i <= n; i += lowbit(i))for (int j = y; j <= m; j += lowbit(j))t1[i][j] += d, t2[i][j] += x * d, t3[i][j] += y * d, t4[i][j] += x * y * d;
}int query(int x, int y){int ans = 0;for (int i = x; i > 0; i -= lowbit(i))for (int j = y; j > 0; j -= lowbit(j))ans += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] - (x + 1) * t3[i][j] + t4[i][j];return ans;
}int main() {fast;scanf("%s", cc);scanf("%d%d", &n, &m);while (scanf("%s", cc) != EOF){scanf("%d%d%d%d", &a, &b, &c, &d);if (cc[0] == 'L'){scanf("%d", &delta);update(a, b, delta);update(c + 1, d + 1, delta);update(a, d + 1, -delta);update(c + 1, b, -delta);}else printf("%d\n", query(c, d) + query(a - 1, b - 1) - query(a - 1, d) - query(c, b - 1));}return 0;
}