题目链接:https://www.luogu.org/problemnew/show/U22582
链接好像失效了
我用的树套树写法。
all in one 代码:
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 2010
#define MAXM 2010
struct LAZY {
int v, l, r;
};#define MAX_NODE1 (MAXN << 2)
#define MAX_NODE2 (MAXM << 2)
struct SGT2 {
int s[MAX_NODE1][MAX_NODE2], n1, n2;
LAZY lazy1[MAX_NODE1];int lazy2[MAX_NODE1][MAX_NODE2];
inline int ls(int rt) {
return rt << 1;
}inline int rs(int rt) {
return rt << 1 | 1;
}void Init(int _n1, int _n2) {
n1 = _n1;
n2 = _n2;0, ((n1 << 2)+1) * sizeof(int));
memset(lazy1, for (int i = 0; i <= (n1 << 2); ++i) {
0, (n2 << 2) * sizeof(int));
memset(s[i], 0, (n2 << 2) * sizeof(int));
memset(lazy2[i],
}
}void Init(int _n1, int _n2, int a[][MAXM]) {
n1 = _n1;
n2 = _n2;1, 1, n1, a);
Build1(
}void PushUp(int d, int rt) {
s[d][rt] = s[d][ls(rt)] + s[d][rs(rt)];
}void Build2(int d, int rt, int l, int r, int a[MAXM]) {
if (l == r) {
s[d][rt] = a[l];else {
} int mid = (l + r) >> 1;
Build2(d, ls(rt), l, mid, a);1, r, a);
Build2(d, rs(rt), mid+
PushUp(d, rt);
}0;
lazy2[d][rt] =
}void Build1(int rt, int l, int r, int a[][MAXM]) {
if (l == r) {
1, 1, n2, a[l]);
Build2(rt, else {
} int mid = (l + r) >> 1;
Build1(ls(rt), l, mid, a);1, r, a);
Build1(rs(rt), mid+for (int i = 1; i <= (n2 << 2); ++i)
s[rt][i] = s[ls(rt)][i] + s[rs(rt)][i];
}0, 0, 0};
lazy1[rt] = LAZY{
}void PushDown2(int d, int rt, int l, int mid, int r) {
if (lazy2[d][rt]) {
lazy2[d][ls(rt)] += lazy2[d][rt];
lazy2[d][rs(rt)] += lazy2[d][rt];1);
s[d][ls(rt)] += lazy2[d][rt] * (mid - l +
s[d][rs(rt)] += lazy2[d][rt] * (r - mid);0;
lazy2[d][rt] =
}
}void Add2(int d, int rt, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
1) * v;
s[d][rt] += (r - l +
lazy2[d][rt] += v;else {
} int mid = (l + r) >> 1;
PushDown2(d, rt, l, mid, r);if (L <= mid) Add2(d, ls(rt), l, mid, L, R, v);
if (mid < R) Add2(d, rs(rt), mid+1, r, L, R, v);
PushUp(d, rt);
}
}void PushDown1(int rt, int l, int mid, int r) {
int& v = lazy1[rt].v, L = lazy1[rt].l, R = lazy1[rt].r;
if (v) {
lazy1[ls(rt)].v += v;
lazy1[rs(rt)].v += v;1, 1, n2, L, R, v * (mid - l + 1));
Add2(ls(rt), 1, 1, n2, L, R, v * (r - mid));
Add2(rs(rt), 0;
v =
}
}//return the width that is modified
int Add1(int rt, int l, int r, int L1, int R1, int L2, int R2, int v) {
int cnt = 0;
if (L1 <= l && r <= R1) {
1;
cnt = r - l + 1, r);
PushDown1(rt, l, (l + r) >>
lazy1[rt] = LAZY{v, L2, R2};else {
} int mid = (l + r) >> 1;
PushDown1(rt, l, mid, r);if (L1 <= mid) cnt = Add1(ls(rt), l, mid, L1, R1, L2, R2, v);
if (mid < R1) cnt += Add1(rs(rt), mid+1, r, L1, R1, L2, R2, v);
}1, 1, n2, L2, R2, v * cnt);
Add2(rt, return cnt;
}
int Sum1(int rt, int l, int r, int L1, int R1, int L2, int R2) {
if (L1 <= l && r <= R1) {
return Sum2(rt, 1, 1, n2, L2, R2);
else {
} int ans = 0, mid = (l + r) >> 1;
PushDown1(rt, l, mid, r);if (L1 <= mid) ans = Sum1(ls(rt), l, mid, L1, R1, L2, R2);
if (mid < R1) ans += Sum1(rs(rt), mid+1, r, L1, R1, L2, R2);
return ans;
}
}int Sum2(int d, int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return s[d][rt];
else {
} int ans = 0, mid = (l + r) >> 1;
PushDown2(d, rt, l, mid, r);if (L <= mid) ans = Sum2(d, ls(rt), l, mid, L, R);
if (mid < R) ans += Sum2(d, rs(rt), mid+1, r, L, R);
return ans;
}
}
};
int main() {
int n, m, q;
static int a[MAXN][MAXM];
static SGT2 sgt2;
"%d%d%d", &n, &m, &q);
scanf(for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
"%d", a[i] + j);
scanf(
}
}
sgt2.Init(n, m, a);
while (q--) {
int p, x1, y1, x2, y2;
"%d%d%d%d%d", &p, &x1, &y1, &x2, &y2);
scanf(if (1 == p) {
"%d\n", sgt2.Sum1(1, 1, n, x1, x2, y1, y2));
printf(else {
} int v;
"%d", &v);
scanf(1, 1, n, x1, x2, y1, y2, v);
sgt2.Add1(
}
}
return 0;
}
封装型代码:
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 2010
#define MAXM 2010
inline int ls(int rt) {
return rt << 1;
}inline int rs(int rt) {
return rt << 1 | 1;
}#define MAX_NODE_SEGTREE (MAXM<<2)
template<typename T>
struct SGT {
T sum[MAX_NODE_SEGTREE], lazy[MAX_NODE_SEGTREE];
void Init(int n) {
0, (n<<2) * sizeof(T));
memset(sum, 0, (n<<2) * sizeof(T));
memset(lazy,
}void PushUp(int rt) {
sum[rt] = sum[ls(rt)] + sum[rs(rt)];
}void Build(int rt, int l, int r, int arr[]) {
if (l == r) {
sum[rt] = arr[l];else {
} int mid = (l+r) >> 1;
Build(ls(rt), l, mid, arr);1, r, arr);
Build(rs(rt), mid+
PushUp(rt);
}0;
lazy[rt] =
}void PushDown(int rt, int l, int mid, int r) {
if (lazy[rt]) {
lazy[ls(rt)] += lazy[rt];
lazy[rs(rt)] += lazy[rt];1);
sum[ls(rt)] += lazy[rt] * (mid - l +
sum[rs(rt)] += lazy[rt] * (r - mid);0;
lazy[rt] =
}
}void Add(int rt, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
lazy[rt] += v;1) * v;
sum[rt] += (T)(r - l + else {
} int mid = (l + r) >> 1;
PushDown(rt, l, mid, r);if (L <= mid)
Add(ls(rt), l, mid, L, R, v);if (mid < R)
1, r, L, R, v);
Add(rs(rt), mid+
PushUp(rt);
}
}int rt, int l, int r, int L, int R) {
T Sum(if (L <= l && r <= R)
return sum[rt];
0;
T ans = int mid = (l + r) >> 1;
PushDown(rt, l, mid, r);if (L <= mid)
ans = Sum(ls(rt), l, mid, L, R);if (mid < R)
1, r, L, R);
ans += Sum(rs(rt), mid+return ans;
}
};
#define MAX_NODE1 (MAXN << 2)
template<typename T>
struct LAZY {
T v;int l, r;
};template<typename T>
struct SGT2 {
SGT<T> s[MAX_NODE1];int n2;
LAZY<T> lazy[MAX_NODE1];
void Init(int n1, int _n2) {
n2 = _n2;0, ((n1 << 2)+1) * sizeof(int));
memset(lazy, for (int i = 0; i <= (n1 << 2); ++i)
s[i].Init(n2);
}void Init(int n1, int _n2, int a[][MAXM]) {
n2 = _n2;1, 1, n1, a);
Build(
}void Build(int rt, int l, int r, int a[][MAXM]) {
if (l == r) {
1, 1, n2, a[l]);
s[rt].Build(else {
} int mid = (l + r) >> 1;
Build(ls(rt), l, mid, a);1, r, a);
Build(rs(rt), mid+for (int i = 1; i <= (n2 << 2); ++i)
s[rt].sum[i] = s[ls(rt)].sum[i] + s[rs(rt)].sum[i];
}0, 0, 0};
lazy[rt] = LAZY<T>{
}void PushDown(int rt, int l, int mid, int r) {
T& v = lazy[rt].v, L = lazy[rt].l, R = lazy[rt].r;if (v) {
lazy[ls(rt)].v += v;
lazy[rs(rt)].v += v;1, 1, n2, L, R, v * (mid - l + 1));
s[ls(rt)].Add(1, 1, n2, L, R, v * (r - mid));
s[rs(rt)].Add(0;
v =
}
}//return the width that is modified
int Add(int rt, int l, int r, int L1, int R1, int L2, int R2, int v) {
int cnt = 0;
if (L1 <= l && r <= R1) {
1;
cnt = r - l + 1, r);
PushDown(rt, l, (l + r) >>
lazy[rt] = LAZY<T>{v, L2, R2};else {
} int mid = (l + r) >> 1;
PushDown(rt, l, mid, r);if (L1 <= mid) cnt = Add(ls(rt), l, mid, L1, R1, L2, R2, v);
if (mid < R1) cnt += Add(rs(rt), mid+1, r, L1, R1, L2, R2, v);
}1, 1, n2, L2, R2, v * cnt);
s[rt].Add(return cnt;
}
int rt, int l, int r, int L1, int R1, int L2, int R2) {
T Sum(if (L1 <= l && r <= R1) {
return s[rt].Sum(1, 1, n2, L2, R2);
else {
} 0;
T ans = int mid = (l + r) >> 1;
PushDown(rt, l, mid, r);if (L1 <= mid) ans = Sum(ls(rt), l, mid, L1, R1, L2, R2);
if (mid < R1) ans += Sum(rs(rt), mid+1, r, L1, R1, L2, R2);
return ans;
}
}
};
int main() {
int n, m, q;
static int a[MAXN][MAXM];
static SGT2<int> sgt2;
"%d%d%d", &n, &m, &q);
scanf(for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
"%d", a[i] + j);
scanf(
}
}
sgt2.Init(n, m, a);
while (q--) {
int p, x1, y1, x2, y2;
"%d%d%d%d%d", &p, &x1, &y1, &x2, &y2);
scanf(if (1 == p) {
"%d\n", sgt2.Sum(1, 1, n, x1, x2, y1, y2));
printf(else {
} int v;
"%d", &v);
scanf(1, 1, n, x1, x2, y1, y2, v);
sgt2.Add(
}
}
return 0;
}