laekov

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]);

}