CDQ分治是分治(归并,逆序对),整体二分是二分查找。

CDQ 分治

cdq 在论文中以两道题来介绍了一类分治算法。
其核心在于计算左半部分对右半部分的影响。
按论文的介绍顺序可以粗糙地分为两类。
第一类和dp有关,参见动态规划中的单调性优化的斜率优化部分。当然计算凸壳并不是cdq分治做dp唯一的用处。比如可以写Hackerrank里101hack这个比赛的Maximizing Mission Points体会一下。
下面我们介绍第二类,用于替代裸数据结构题的分治。
先看下面这个讲解。
意识流
Hint:当前分治处理到的区间长度为 $L$, 那么清理外部数组的复杂度必须是 $O(N)$ 左右,否则总复杂度不是 $O(NlogN)$。可以储存下这次处理过的操作,递归结束时还原。

下面开始胡说八道流
CDQ 分治的过程和归并排序很像。
考虑各个操作之间存在时间顺序和影响顺序。

举个简单例子,对于一个数列,影响序的含义是修改2的点权会影响3的前缀和,而修改3的点权不影响2的前缀和。
时间序就不解释了。

操作 A 对操作 B 实际上有贡献的充要条件是,时间序 A < B, 影响序 A < B。

算法过程是这样的:
假设输入序列按时间序递增(一般的确如此),我们将左、右两部分同时按影响序排序,然后合并成一个影响序递增的序列。合并过程中只处理左半部分修改,右半部分查询。然后很容易按归纳法证明正确性了。

然后你发现时间序也是一种影响序,所以以上均为我瞎bb。世界上只有元素之前会不会偏序影响的道理。

Prob Hint
BZOJ1176 Mokia 入门题
BZOJ2716 天使玩偶 网上的题解很容易懂。
BZOJ3295 动态逆序对 数列中第 x 个数 y 看成平面上一点 (x,y)
答案的变化量是一个点左上角和右下角的点的数量。
BZOJ2683 简单题 双倍经验
1935 Tree 园丁的烦恼 三倍经验,意义不大
BZOJ3262 陌上花开 注意去重。第一次排序的时候三维都要比较,强行造出时间序

感觉我的代码还是比较清晰的,希望能帮到你。

//动态逆序对
#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
typedef long long ll;
const int N = 2e5 + 10;
struct Q{int x,y,i;}qu[N], qq[N], mg[N];
int n, m, th[N], a[N], mxv;
ll ans[N];
inline int lowbit(int x) {return x&-x;}
inline void add(int p, int v) {
    while (p <= mxv) a[p] += v, p += lowbit(p);
}
inline int pre(int p) {
    int s = 0;
    while (p) s += a[p], p -= lowbit(p);
    return s;
}
inline int sum(int l, int r) {return pre(r) - pre(l - 1);}
std::stack<int> rec;
void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    solve(l, mid), solve(mid + 1, r);
    int i = l, j = mid + 1, sz = 0;
    while (i <= mid || j <= r) {
        if (i > mid || (j <= r && qq[j].x < qq[i].x)) {
            int f = qq[j].y < 0 ? -1 : 1;
            ans[qq[j].i] += f*sum(f*qq[j].y + 1, mxv);
            mg[sz++] = qq[j++];
        }
        else {
            int f = qq[i].y < 0 ? -1 : 1;
            add(f*qq[i].y, f);
            rec.push(i);
            mg[sz++] = qq[i++];
        }
    }
    while (!rec.empty()) {
        int x = rec.top(), f = qq[x].y < 0 ? -1 : 1;
        rec.pop();
        add(f*qq[x].y, -f);
    }
    memcpy(qq + l, mg, sizeof(Q)*sz);
}
int main() {
//    freopen("input", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &qu[i].y), qu[i].i = i, qu[i].x = i, th[qu[i].y] = i;
    for (int i = n + 1; i <= n + m; i++) scanf("%d", &qu[i].y), qu[i].x = th [qu[i].y], qu[i].i = i, qu[i].y*=-1;
    for (int i = 1; i <= n; i++) mxv = std::max(mxv, qu[i].y);
    memcpy(qq, qu, sizeof(qu));
    solve(1, n + m);
    for (int i = 1; i <= n + m; i++) {
        qq[i] = qu[i];
        qq[i].x = n + 1 - qq[i].x;
        int f = qq[i].y < 0 ? -1 : 1;
        qq[i].y = (mxv + 1 - f*qq[i].y)*f;
    }
    solve(1, n + m);
    for (int i = 1; i <= n + m; i++) ans[i] += ans[i - 1];
    for (int i = n; i < n + m; i++) printf("%lld\n", ans[i]);
}
//陌上花开
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
const int N = 1e5 + 10, K = 2e5 + 10;
struct P{int s, x, y, a, w;
    bool operator<(const P& b)const{
        if (s != b.s) return s < b.s;
        else if (x != b.x) return x < b.x;
        else return y < b.y;
    }
    bool operator==(const P& b)const {return s == b.s && x == b.x && y == b.y;}
}qu[N], mg[N];
int n, k, ans[N], a[K];
inline int lowbit(int x){return x&-x;}
inline void add(int p, int v) {
    while (p <= k) a[p] += v, p += lowbit(p);
}
inline int pre(int p) {
    int s = 0;
    while (p) s += a[p], p -= lowbit(p);
    return s;
}
std::stack<int> rec;
void solve(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    solve(l, mid), solve(mid + 1, r);
    int i = l, j = mid + 1, sz = 0;
    while (i <= mid || j <= r) { if (i > mid || (j <= r && qu[j].x < qu[i].x)) {
            qu[j].a += pre(qu[j].y);
            mg[sz++] = qu[j++];
        }
        else {
            add(qu[i].y, qu[i].w);
            rec.push(i);
            mg[sz++] = qu[i++];
        }
    }
    while (!rec.empty()) {
        int x = rec.top();
        rec.pop();
        add(qu[x].y, -qu[x].w);
    }
    memcpy(qu + l, mg, sizeof(P)*sz);
}
int main() {
//  freopen("input", "r", stdin);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &qu[i].s, &qu[i].x, &qu[i].y);
    }
    std::sort(qu + 1, qu + 1 + n);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        int j = i;
        while (j + 1 <= n && qu[j + 1] == qu[i]) j++;
        mg[++tot] = qu[i];
        mg[tot].w = j - i + 1;
        i = j;
    }
    memcpy(qu, mg, sizeof(mg));
    solve(1, tot);
    for (int i = 1; i <= n; i++) ans[qu[i].a + qu[i].w - 1] += qu[i].w;
    for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
}

See Also

CDQ分治 by Fancy
CDQ分治 by zyk1997

整体二分

入门
带修改

自己脑补吧。
带修改时天然时间序方便了很多,并且我们可以把修改只分到一侧。

Prob Hint
BZOJ2527 Meteors 注意会爆long long…
BZOJ3110 K大数查询 还是会爆long long