题意很好理解，不说了
题解就是每次把值压缩成一维，比如x上，这样就可以求出任意宽度的整个竖条的和。
如这张图，求的是s5-(s1+s3+s7+s9)
因为可以求出一整竖条和一整横条，我们可以求出是s2+s5+s8 也可以求出s4+s5+s6 当然也很容易求出总面积S
那么S-(s2+s5+s8)-(s4+s5+s6) = s1+s3+s7+s9-s5
对，答案已经出来了，很简单。
以后看到这种求解公式十分奇怪的题，就要算一算是不是能构造出很简单的公式。
注意这题用cin cout 会超时！因为codeforce是单样例，所以都忘了这点，t了好多次……T^T
区间更新＋区间查询，线段树＋lazy操作 （514ms
#include <stdio.h> typedef long long ll; const int N = ;
ll tx[N<<], ty[N<<], fx[N<<], fy[N<<];
int yl, yr, yv;
#define lson (o<<1)
#define rson ((o<<1)+1) void pushdown(ll tr[], ll fg[], int o, int l, int r)
{
if (fg[o]) {
fg[lson] += fg[o];
fg[rson] += fg[o];
int m = (l+r) >> ;
tr[lson] += fg[o] * (m-l+);
tr[rson] += fg[o] * (r-m);
fg[o] = ;
}
} void add(ll tr[], ll fg[], int o, int l, int r)
{
if (l == r) {
tr[o] += yv;
return ;
}
if (yl <= l && yr >= r) {
tr[o] += (ll)yv * (r-l+);
fg[o] += yv;
return ;
}
pushdown(tr, fg, o, l, r);
int m = (l+r) >> ;
if (yl <= m) add(tr, fg, lson, l, m);
if (yr > m) add(tr, fg, rson, m+, r);
tr[o] = tr[lson] + tr[rson];
} ll query(ll tr[], ll fg[], int o, int l, int r)
{
if (l >= yl && r <= yr) {
return tr[o];
}
pushdown(tr, fg, o, l, r);
int m = (l+r) >> ;
ll ans = ;
if (m >= yl) ans += query(tr, fg, o<<, l, m);
if (m < yr) ans += query(tr, fg, (o<<)+, m+, r);
return ans;
} int main()
{ int n, m, w;
scanf("%d%d%d", &n, &m, &w);
int op;
int x1, x2, y1, y2;
ll v;
ll tot, ans;
while (w--) {
scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);
if (op) {
yl = , yr = n;
tot = query(tx, fx, , , n);
ans = ;
yl = x1, yr = x2;
ans += query(tx, fx, , , n);
yl = y1, yr = y2;
ans += query(ty, fy, , , m);
printf("%lld\n", ans-tot);
} else {
scanf("%lld", &v);
yl = x1, yr = x2, yv = v*(y2-y1+);
add(tx, fx, , , n);
yl = y1, yr = y2, yv = v*(x2-x1+);
add(ty, fy, , , m);
}
}
return ;
}
顺便学习了一下树状数组的区间操作（202ms 时间空间都优于线段树
#include <stdio.h>
typedef long long ll;
const int MAXN = ;
int lowbit(int x) { return x&-x; }
struct tree_array {
struct tree_array_single {
int N;
ll arr[MAXN];
void add(int x, ll v) { while(x <= N) arr[x] += v, x += lowbit(x); }
ll sum(int x) { ll sum = ; while(x) sum+=arr[x], x-=lowbit(x); return sum; }
} T1, T2;
void add(int x, ll v) { T1.add(x, v); T2.add(x, x*v); }
void update(int L, int R, ll v) { add(L, v); add(R+, -v); }
ll sum(int x) { return (x+)*T1.sum(x)-T2.sum(x); }
ll query(int L,int R) { return sum(R)-sum(L-); }
} tx, ty;
int main()
{
//freopen("in.txt", "r", stdin);
int n, m, w;
scanf("%d%d%d", &n, &m, &w);
int op;
int x1, x2, y1, y2;
ll v;
tx.T1.N = tx.T2.N = n;
ty.T1.N = ty.T2.N = m;
ll tot = ;
while (w--) {
scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);
if (op) {
ll ans = tx.query(x1, x2) + ty.query(y1, y2);
printf("%lld\n", ans-tot);
} else {
scanf("%lld", &v);
tot += (y2-y1+)*(x2-x1+)*v;
tx.update(x1, x2, v*(y2-y1+));
ty.update(y1, y2, v*(x2-x1+));
}
}
return ;
}