一、关于CDQ分治
现在给你很多操作，每次给出\(pos\)以及\(x\)，表示\(pos\)位置上的数加上x，然后给出很多询问，每次问\(l\)到\(r\)之间的和。
显然这个东西\(O(n)\)是可以解决的。但是如果操作和询问交叉的话（不用树状数组），就不能用这种方法了。但是可以发现如果一个点在\(i\)的时刻被加了一个数，那么在\(i\)及以后的时刻这个位置都会加上这个数（因为不会存在删除的操作）。
所以可以尝试利用这种不删除的特点。我们考虑一个做法。假设要处理\([l,r]\)之间的操作。我们先处理\([l,\lfloor (l+r)/2 \rfloor]\)之间的操作，再处理\([\lfloor (l+r)/2 \rfloor+1,r]\)之间的操作，再考虑左边对右边的影响。
那这道就可以变成刚开始的情况了。
二、题目
1.Luogu P4390 [BOI2007]Mokia 摩基亚
题意：
有n次操作，每次操作要么给一个二维坐标的点加上一个数，要么询问某个矩形内的数的和。考虑CDQ和差分。
题解：
在合并左右的影响时，用差分的思想。如果求的是\((x1,y1)\)到\((x2,y2)\)的和。就是求横坐标在\(1\)至\(x1-1\)间纵坐标在\(y1\)至\(y2\)的树的和，还横坐标在\(1\)至\(x2\)间纵坐标在\(y1\)至\(y2\)的树的和。考虑扫描线，把询问拆成两个询问，处理每个询问前把所有横坐标在当前询问之前的点都加入当中，用树状数组或线段数维护即可。
代码：
#include#include #include #include #include #include using namespace std;const int MAXN = 200000;const int MAXX = 2000000;struct Point { int x, y, w;} b[MAXN + 5];struct Query { int id, flag, x, sy, ey;} c[MAXN + 5 << 1];int ans[MAXN + 5], a[MAXN + 5][5], opt, n;bool cmpb(Point a, Point b) { return a.x < b.x; }bool cmpc(Query a, Query b) { return a.x < b.x; }class BinaryIndexTree { private: int c[MAXX + 5]; void _add(int x, int y) { for (int i = x; i <= MAXX; i += i & -i) c[i] += y; } void _dec(int x, int y) { for (int i = x; i <= MAXX; i += i & -i) c[i] -= y; } int _query(int x) { int ret = 0; for (int i = x; i; i -= i & -i) ret += c[i]; return ret; } public: void add(int x, int y) { _add(x, y); } int query(int x, int y) { return _query(y) - _query(x - 1); } void dec(int x, int y) { _dec(x, y); }} bit;void cdq(int l, int r) { if (l == r) return; int mid = l + r >> 1; cdq(l, mid); cdq(mid + 1, r); int bcnt = 0, ccnt = 0; for (int i = l; i <= mid; ++i) if (a[i][0] == 1) b[++bcnt] = (Point){a[i][1], a[i][2], a[i][3]}; for (int i = mid + 1; i <= r; ++i) if (a[i][0] == 2) { c[++ccnt] = (Query){i, -1, a[i][1] - 1, a[i][2], a[i][4]}; c[++ccnt] = (Query){i, 1, a[i][3], a[i][2], a[i][4]}; } sort(b + 1, b + bcnt + 1, cmpb); sort(c + 1, c + ccnt + 1, cmpc); int bptr = 0; for (int i = 1; i <= ccnt; ++i) { while (bptr < bcnt && b[bptr + 1].x <= c[i].x) { bit.add(b[bptr + 1].y, b[bptr + 1].w); ++bptr; } ans[c[i].id] += c[i].flag * bit.query(c[i].sy, c[i].ey); } while (bptr--) bit.dec(b[bptr + 1].y, b[bptr + 1].w);}int main() { scanf("%d", &opt); while (opt != 3) { if (opt == 1) { a[++n][0] = opt; scanf("%d%d%d", &a[n][1], &a[n][2], &a[n][3]); } else if (opt == 2) { a[++n][0] = opt; scanf("%d%d%d%d", &a[n][1], &a[n][2], &a[n][3], &a[n][4]); } scanf("%d", &opt); } cdq(1, n); for (int i = 1; i <= n; ++i) if (a[i][0] == 2) printf("%d\n", ans[i]); return 0;}
2.Luogu P3810 【模板】三维偏序（陌上花开）
题意：
题目很简洁
题解：
这道题目和上一题其实差不多，我们考虑将一维排序，然后对于每个数只找前面的满足条件的。问题是第一维相同的可能统计不到，所以后统计答案的时候对于每个相同的三元组，答案为最大的那个的值。
代码：
#include#include #include #include #include #include