传送门
之前听别人说CDQ分治不难学，今天才知道果真如此。之前一直为自己想不到CDQ的方法二很不爽，今天终于是想出来了一道了，太弱……
cdq分治主要就是把整段区间分成两半，然后用左区间的值去更新右区间的答案，每次把区间折半。对于本题来说时间复杂度T(N)=T(N/2)+O(NlogN)
T(N)=O(Nlog2N)
/**************************************************************
Problem: 2683
Language: C++
Result: Accepted
Time:6204 ms
Memory:35184 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 200005
struct Node {
int t, x, y, v, k;
inline bool operator < (const Node&r) const {
if(x == r.x && y == r.y) return t < r.t;
else if(x == r.x) return y < r.y;
else return x < r.x;
}
} q[MAXN << 2], nq[MAXN << 2];
int n, cnt, ans;
inline void GET(int &n) {
n = 0; char c;
do c = getchar(); while('0' > c || c > '9');
do n = n * 10 + c - '0', c = getchar(); while('0' <= c && c <= '9');
}
namespace BIT {
int t[MAXN << 2];
inline void Add(int x, int v) {
for(; x <= n; x += x&-x) t[x] += v;
}
inline int Query(int x, int s = 0) {
for(; x; x -= x&-x) s+=t[x];
return s;
}
}
void cdq(int l, int r) {
if(l >= r) return;
using namespace BIT;
int mid = (l + r) >> 1, lp = l, rp = mid+1;
for(int i = l; i <= r; ++ i)
if(q[i].t <= mid && q[i].k == 1) Add(q[i].y, q[i].v);
else if(q[i].t > mid && q[i].k == 2) q[i].v += Query(q[i].y);
for(int i = l; i <= r; ++ i) {
if(q[i].t <= mid && q[i].k == 1) Add(q[i].y, -q[i].v);
if(q[i].t <= mid) nq[lp ++] = q[i];
else nq[rp ++] = q[i];
}
for(int i = l; i <= r; ++ i) q[i] = nq[i];
cdq(l, mid); cdq(mid+1, r);
}
int main() {
scanf("%d", &n);
int op, x, y, a, b;
while(~scanf("%d", &op) && 3 != op) {
if(1 == op) {
GET(x); GET(y); GET(a);
q[++ cnt] = { cnt, x, y, a, 1 };
}
else {
GET(x); GET(y); GET(a); GET(b);
q[++ cnt] = { cnt, x-1, y-1, 0, 2 };
q[++ cnt] = { cnt, x-1, b, 0, 2 };
q[++ cnt] = { cnt, a, y-1, 0, 2 };
q[++ cnt] = { cnt, a, b, 0, 2 };
}
}
sort(q+1, q+cnt+1);
cdq(1, cnt);
for(int i = 1; i <= cnt; ++ i)
if(q[i].k == 2) {
ans = q[i].v - q[i+1].v - q[i+2].v + q[i+3].v;
printf("%d\n", ans); i += 3;
}
return 0;
}