cdq分治第一题。
最近的主题是数据结构，这玩意应该也算一种和莫队一样厉害的黑暗大法吧。有些需要你把在线写得足够厉害的题可以用这玩意来水。
写起来很像归并排序，按时间分治，然后再按某个坐标之类的玩意归并一下，归并的时候像求逆序对一样做，计算一边对另一边的贡献，顺便用点啥数据结构维护一下之类的。
这题有点像上帝造题七分钟。不过w的范围显然不是让你写二维树状数组。感觉那题可以用cdq水过，不过cdq好像不能用简单的二维树状数组，至少要动态一下啥的，然后空间就bye了。
这题就是按x排序查询y。课件上的原题。
另外依然不会迗代，还是写的递归。（找到了fft的感觉）
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long qw;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
struct query {
int t, x, y, v;
inline query(int t0 = 0, int x0 = 0, int y0 = 0, int v0 = 0) {
t = t0, x = x0, y = y0, v = v0;
}
};
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxm = 2000009;
const int maxn = 200009;
qw ans[maxn], t[maxm];
int tmm[maxm], ttm;
int v0, m, n, q;
query a[maxn], b[maxn];
void btChg(int p, int v) {
for (++ p; p <= m; p += (p & -p))
if (tmm[p] < ttm)
tmm[p] = ttm, t[p] = v;
else
t[p] += v;
}
qw btQry(int p) {
qw s = 0;
for (++ p; p; p -= (p & -p))
if (tmm[p] < ttm)
tmm[p] = ttm, t[p] = 0;
else
s += t[p];
return s;
}
void cdq(int l, int r) {
if (l + 1 == r)
return;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid, r);
++ ttm;
for (int i = l, j = mid, k = l; i < mid || j < r;)
if (i < mid && (a[i]. x <= a[j]. x || j == r)) {
if (!a[i]. t)
btChg(a[i]. y, a[i]. v);
b[k ++] = a[i ++];
}
else {
if (a[j]. t) {
qw v = btQry(a[j]. y);
if (a[j]. t == 1)
ans[a[j]. v] += v;
else
ans[a[j]. v] -= v;
}
b[k ++] = a[j ++];
}
for (int i = l; i < r; ++ i)
a[i] = b[i];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(ans, 0, sizeof(ans));
memset(tmm, 0, sizeof(tmm));
ttm = 0;
readInt(v0);
readInt(m);
++ m;
n = 0;
q = 0;
while (1) {
int opt, x, y, u, v;
readInt(opt);
if (opt == 3)
break;
else if (opt == 2) {
readInt(x);
readInt(y);
readInt(u);
readInt(v);
-- x;
-- y;
a[n ++] = query(1, u, v, q);
a[n ++] = query(1, x, y, q);
a[n ++] = query(2, u, y, q);
a[n ++] = query(2, x, v, q);
ans[q] = (qw)v0 * (u - x) * (v - y);
++ q;
}
else {
readInt(x);
readInt(y);
readInt(v);
a[n ++] = query(0, x, y, v);
}
}
cdq(0, n);
for (int i = 0; i < q; ++ i)
printf("%d\n", (int)ans[i]);
}