BZOJ2683 簡單題（CDQ分治）

傳送門
之前聽別人說CDQ分治不難學，今天才知道果真如此。之前一直為自己想不到CDQ的方法二很不爽，今天終于是想出來了一道了，太弱……
cdq分治主要就是把整段區間分成兩半，然后用左區間的值去更新右區間的答案，每次把區間折半。對于本題來說時間復雜度T(N)=T(N/2)+O(NlogN)
T(N)=O(Nlog2N)

/**************************************************************Problem: 2683Language: C++Result: AcceptedTime:6204 msMemory: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;
}