链接
思路
cdq入门题，拆成4个矩阵，然后cdq。
代码
/**************************************************************
Problem: 1176
User: gryz2016
Language: C++
Result: Accepted
Time:2652 ms
Memory:13012 kb
****************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
const int N = 2e5 + 7;
int read() {
int x = 0, f = 1; char s = getchar();
for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
return x * f;
}
int n, a[N], ans[N];
struct ask {
int opt, x, y, w, id;
ask(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) {
opt = a, x = b, y = c, w = d, id = e;
}
bool operator < (const ask &b) const {
return x == b.x ? opt < b.opt : x < b.x;
}
} Q[N], tmp[N];
int lsh_y[N << 1];
namespace BIT {
int sum[N], maxn;
void add(int id, int w) {
for (int i = id; i <= maxn; i += lowbit(i)) sum[i] += w;
}
int query(int x) {
int ans = 0;
for (int i = x; i >= 1; i -= lowbit(i)) ans += sum[i];
return ans;
}
}
void cdq(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);
int p = l, q = mid + 1, js = l;
while (p <= mid && q <= r) {
if (Q[p] < Q[q]) {
if (Q[p].opt == 1) BIT::add(Q[p].y, Q[p].w);
tmp[js++] = Q[p++];
} else {
if (Q[q].opt == 2) ans[Q[q].id] += Q[q].w * BIT::query(Q[q].y);
tmp[js++] = Q[q++];
}
}
if (p <= mid) {
for (int i = l; i < p; ++i) if (Q[i].opt == 1) BIT::add(Q[i].y, -Q[i].w);
while (p <= mid) tmp[js++] = Q[p++];
} else {
while (q <= r) {
if (Q[q].opt == 2) ans[Q[q].id] += Q[q].w * BIT::query(Q[q].y);
tmp[js++] = Q[q++];
}
for (int i = l; i <= mid; ++i) if (Q[i].opt == 1) BIT::add(Q[i].y, -Q[i].w);
}
for (int i = l; i <= r; ++i) Q[i] = tmp[i];
}
int main() {
// freopen("a.in", "r", stdin);
int S = read(), W = read(), n = 0, DSR = 0;
while (233) {
int opt = read();
if (opt == 3) break;
if (opt == 1) {
int x = read(), y = read(), w = read();
Q[++n] = ask(opt, x, y, w), lsh_y[++lsh_y[0]] = Q[n].y;
} else {
++DSR;
int a = read(), b = read(), x = read(), y = read();
if (x && y) Q[++n] = ask(opt, x, y, 1, DSR), lsh_y[++lsh_y[0]] = Q[n].y;
if (a - 1 && b - 1) Q[++n] = ask(opt, a - 1, b - 1, 1, DSR), lsh_y[++lsh_y[0]] = Q[n].y;
if (a - 1 && y) Q[++n] = ask(opt, a - 1, y, -1, DSR), lsh_y[++lsh_y[0]] = Q[n].y;
if (x && b - 1) Q[++n] = ask(opt, x, b - 1, -1, DSR), lsh_y[++lsh_y[0]] = Q[n].y;
}
}
sort(lsh_y + 1, lsh_y + 1 + lsh_y[0]);
lsh_y[0] = unique(lsh_y + 1, lsh_y + 1 + lsh_y[0]) - lsh_y - 1;
for (int i = 1; i <= n; ++i) Q[i].y = lower_bound(lsh_y + 1, lsh_y + 1 + lsh_y[0], Q[i].y) - lsh_y;
BIT::maxn = lsh_y[0] + 1;
cdq(1, n);
for (int i = 1; i <= DSR; ++i) printf("%d\n", ans[i]);
return 0;
}