算法 - 整体二分 & CDQ分治

Posted on 2017-08-03 Edited on 2018-08-17 In Algorithms Disqus:

整体二分

资料

具体见 2013 年集训队论文《浅谈数据结构题的几个非经典解法》（作者：许昊然）。
本文假设读者已经读过这篇论文中整体二分的部分。

限制

需要离线
可以二分答案
修改操作，要求对于一次查询，前面的修改操作可以交换顺序而不影响查询结果
贡献可以累加
注意将操作（包括询问）分离到两个新的答案区间这个过程的复杂度应该和操作数的个数相关，而不能和以下两项相关：
- 总的区间（就是最初的答案区间）
- 尤其是序列总长，通常指的是询问区间的长度

例题

静态区间第 k 大

题目：poj 2104, hdu 2665, EOJ 3315 经典题。给出 n 个数，询问区间内第k大的数。通常做法是主席树。

整体二分答案
目标：对于在答案区间 [l, r] 内的询问，分发到 [l, mid] 和 [mid + 1, r]，这个过程要求时间复杂度与询问个数或者答案区间长度相关而不能与 n 有关。
筛选出 n 个数中大小在 [mid + 1, r] 之间的数的位置，通过二分查找计算这些数有几个落在每个询问的区间内，存到临时答案数组 tmp_ans 中。
对于询问 q[i], 如果 k-1 < tmp_ans[i] + q[i].cur，说明答案落在 [mid + 1, r] 中，反之，则落在 [l, mid] 中，由于大于 mid 的数的贡献不变，所以存在 q[i].cur 中，之后就不需要考虑大于 mid 的数了。
至此，成功划分为子问题。
复杂度 \(O((N + Q)\log n\log C)\)，\(C\) 是数值范围
实际上用整体二分的时间消耗和主席树很接近，代码长度也没有优势，但是很省空间。

代码 (EOJ 3315):

#include <bits/stdc++.h>
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const int MAX = 1E9 + 10;
const int maxn = 1E5 + 100;
struct Q {
    int l, r, k, cur, ans;
};
struct P {
    int id, v;
    bool operator < (const P& rhs) const {
        return v < rhs.v;
    }
};
Q query[maxn];
P p[maxn];
int n, m, t, pos[maxn], pos_sz, tmp_ans[maxn];

void go(const vector<Q*>& q, int l, int r) {
    if (q.empty()) return;
    if (l == r) {
        FOR (i, 0, q.size()) q[i]->ans = l;
        return;
    }
    int mid = l + ((r - l) >> 1);
    pos_sz = 0;
    FOR (it, upper_bound(p, p + n, P{0, mid}), upper_bound(p, p + n, P{0, r}))
        pos[pos_sz++] = it->id;
    sort(pos, pos + pos_sz);
    FOR (i, 0, q.size())
        tmp_ans[i] = upper_bound(pos, pos + pos_sz, q[i]->r) -
                     lower_bound(pos, pos + pos_sz, q[i]->l);
    vector<Q*> qL, qR;
    FOR (i, 0, q.size()) {
        if (q[i]->k - 1 < q[i]->cur + tmp_ans[i]) {
            qR.push_back(q[i]);
        } else {
            qL.push_back(q[i]);
            q[i]->cur += tmp_ans[i];
        }
    }
    go(qL, l, mid);
    go(qR, mid + 1, r);
}

int main() {
    cin >> n >> m;
    FOR (i, 0, n) {
        scanf("%d", &t);
        p[i].v = t;
        p[i].id = i + 1;
    }
    sort(p, p + n);
    vector<Q*> q;
    FOR (i, 0, m) {
        scanf("%d%d%d", &query[i].l, &query[i].r, &query[i].k);
        query[i].cur = 0;
        q.push_back(&query[i]);
    }
    go(q, -MAX, MAX);
    FOR (i, 0, m) printf("%d\n", q[i]->ans);
}

动态区间第 k 大

题目：hdu 5412。与之前的题目相比，额外支持一个操作，修改一个位置上的数。

将修改操作视为删除一个数后插入一个数，一开始的初始状态看做进行了 n 次插入操作。
无论是查询操作还是修改操作，都需要分发到对应子区间内。
利用树状数组来保证单次的复杂度仅与待分发的操作数个数相关。
树状数组使用后进行还原，避免了\(O(n)\)的清空操作

代码

#include <bits/stdc++.h>
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const int maxn = 1E5 + 10;
const int MAX = 1E9 + 10;
struct Q { // tp = 0 -> query, tp = 1 -> modify
    int tp, pos, d, l, r, k, cur, ans;
};
int a[maxn], n, m, q_n, t, l, r, k, pos, c[maxn], tmp_ans[maxn];
Q q[maxn << 1];

inline int lowbit(int x) { return x & -x; }
void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) c[i] += k;
}
int sum(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= lowbit(i)) ret += c[i];
    return ret;
}

void go(const vector<Q*>& q, int l, int r) {
    cerr << l << ' ' << r << endl;
    if (q.empty()) return;
    if (l == r) {
        FOR (i, 0, q.size()) q[i]->ans = l;
        return;
    }
    int mid = l + ((r - l) >> 1);
    FOR (i, 0, q.size())
        if (q[i]->tp && abs(q[i]->d) <= mid) add(q[i]->pos, q[i]->d / abs(q[i]-> d));
        else if (!q[i]->tp) tmp_ans[i] = sum(q[i]->r) - sum(q[i]->l - 1);
    FOR (i, 0, q.size())
        if (q[i]->tp && abs(q[i]->d) <= mid) add(q[i]->pos, -q[i]->d / abs(q[i]-> d));
    vector<Q*> qL, qR;
    FOR (i, 0, q.size())
        if (!q[i]->tp) {
            if (q[i]-> k > tmp_ans[i] + q[i]->cur) {
                qR.push_back(q[i]);
                q[i]->cur += tmp_ans[i];
            } else {
                qL.push_back(q[i]);
            }
        } else {
            if (abs(q[i]->d) <= mid) qL.push_back(q[i]);
            else qR.push_back(q[i]);
        }
    go(qL, l, mid);
    go(qR, mid + 1, r);
}

int main() {
    cin >> n;
    FOR (i, 1, n + 1) {
        scanf("%d", &a[i]);
        q[m++] = Q{1, i, a[i], -1, -1, -1, -1, -1};
    }
    cin >> q_n;
    FOR (i, 0, q_n) {
        scanf("%d", &t);
        if (t == 2) {
            scanf("%d%d%d", &l, &r, &k);
            q[m++] = Q{0, -1, -1, l, r, k, 0, 0};
        } else {
            scanf("%d", &pos);
            q[m++] = Q{1, pos, -a[pos], -1, -1, -1, -1, -1};
            scanf("%d", &a[pos]);
            q[m++] = Q{1, pos, a[pos], -1, -1, -1, -1, -1};
        }
    }
    vector<Q*> query; query.resize(m);
    FOR (i, 0, m) query[i] = &q[i];
    go(query, 1, MAX);
    FOR (i, 0, m)
        if (!q[i].tp)
            printf("%d\n", q[i].ans);
}

CDQ分治

资料

从《Cash》谈一类分治算法的应用.doc （2008集训队论文，陈丹琦）
http://www.cnblogs.com/candy99/p/cdq.html

两类情况

统计

左右分别递归
对左右归并
计算左对右的贡献

优化

左边递归
排序（因为右边没有递归过，所以没办法归并）
计算左对右的贡献
右边递归

注意

LIS 要注意等号的问题。如果划分到两边的这一维相等，要保证左边的向右边的贡献是合理的。如果直接在上一层的结果上进行稳定排序而不是复制一份，可能导致上一层的这部分考虑失效。（概括一下，就是要复制一份给下一层用）
LIS 中只需要第一层用 sort，里面几层用 merge 就可以了。因为第一层的 sort 考虑了贡献累加的问题，对后面几层的要求就没有贡献累加这一条了（只要求如果存在偏序，计算一次贡献）。
无论何时，记得排序去掉一维。

例题

两维 LIS （三维偏序）

为了表现我掌握了 CDQ 分治，所以用了两层 CDQ 而不是 CDQ 套一维数据结构。
有一个重要的技巧，就是如果某一维相等，为了防止产生贡献，按照从右往左的顺序排序（也就是要先查询再修改）。
为什么最后一层可以 merge，而前面的只能 sort 呢？

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 2E5 + 100;
struct P {
    int x, y;
    int* f;
    bool d1, d2;
} a[maxn], b[maxn], c[maxn];
int f[maxn];

void go2(int l, int r) {
    if (l + 1 == r) return;
    int m = (l + r) >> 1;
    go2(l, m); go2(m, r);
    FOR (i, l, m) b[i].d2 = 0;
    FOR (i, m, r) b[i].d2 = 1;
    merge(b + l, b + m, b + m, b + r, c + l, [](const P& a, const P& b)->bool {
            if (a.y != b.y) return a.y < b.y;
            return a.d2 > b.d2;
        });
    int mx = -1;
    FOR (i, l, r) {
        if (c[i].d1 && c[i].d2) *c[i].f = max(*c[i].f, mx + 1);
        if (!c[i].d1 && !c[i].d2) mx = max(mx, *c[i].f);
    }
    FOR (i, l, r) b[i] = c[i];
}

void go1(int l, int r) { // [l, r)
    if (l + 1 == r) return;
    int m = (l + r) >> 1;
    go1(l, m);
    FOR (i, l, m) a[i].d1 = 0;
    FOR (i, m, r) a[i].d1 = 1;
    copy(a + l, a + r, b + l);
    sort(b + l, b + r, [](const P& a, const P& b)->bool {
            if (a.x != b.x) return a.x < b.x;
            return a.d1 > b.d1;
        });
    go2(l, r);
    go1(m, r);
}

int main() {
    FOR (i, 0, maxn) a[i].f = &f[i];
    int T, n; cin >> T;
    while (T--) {
        cin >> n;
        FOR (i, 0, n) scanf("%d", &a[i].x);
        FOR (i, 0, n) scanf("%d", &a[i].y);
        memset(f, 0, sizeof f);
        go1(0, n);
        int ans = 0;
        FOR (i, 0, n) ans = max(ans, f[i]);
        cout << ans + 1 << endl;
    }
}

三维 LIS（四维偏序）

const int N = 8E4 + 100;
struct P {
    int v[4];
    int f;
    bool d[4];
} o[N];
P *b[N], *c[N], *d[N], *e[N];

void go3(int l, int r) {
    if (l + 1 == r) return;
    int m = (l + r) / 2;
    go3(l, m); go3(m, r);
    FOR (i, l, m) d[i]->d[3] = 0;
    FOR (i, m, r) d[i]->d[3] = 1;
    merge(d + l, d + m, d + m, d + r, e + l, [](const P* a, const P* b){
        if (a->v[3] != b->v[3]) return a->v[3] < b->v[3];
        return a->d[3] > b->d[3];
    });
    int mx = -1;
    FOR (i, l, r) {
        if (e[i]->d[1] && e[i]->d[2] && e[i]->d[3]) e[i]->f = max(e[i]->f, mx + 1);
        if (!e[i]->d[1] && !e[i]->d[2] && !e[i]->d[3]) mx = max(mx, e[i]->f);
    }
    copy(e + l, e + r, d + l);
}

void go2(int l, int r) {
    if (l + 1 == r) return;
    int m = (l + r) / 2;
    go2(l, m); go2(m, r);
    FOR (i, l, m) c[i]->d[2] = 0;
    FOR (i, m, r) c[i]->d[2] = 1;
    merge(c + l, c + m, c + m, c + r, d + l, [](const P* a, const P* b){
        if (a->v[2] != b->v[2]) return a->v[2] < b->v[2];
        return a->d[2] > b->d[2];
    });
    copy(d + l, d + r, c + l);
    go3(l, r);
}

void go1(int l, int r) {
    if (l + 1 == r) return;
    int m = (l + r) / 2;
    go1(l, m);
    FOR (i, l, m) b[i]->d[1] = 0;
    FOR (i, m, r) b[i]->d[1] = 1;
    copy(b + l, b + r, c + l);
    sort(c + l, c + r, [](const P* a, const P* b){
        if (a->v[1] != b->v[1]) return a->v[1] < b->v[1];
        return a->d[1] > b->d[1];
    });
    go2(l, r);
    go1(m, r);
}

陌上花开（三维偏序）

题解传送门

线段树分治

简介

将操作存在的时间区间分发到线段树的若干个结点（类似于线段树的区间操作）。
将询问的时间点放在线段树的叶子上。
在这棵线段树上进行 dfs（需要回溯）。
每个操作最多被复制 \(q\log Time_{max}\) 次。

限制

每个操作都作用于一个时间区间，询问只在乎当前时间点有那些操作存在（与操作发生的顺序无关）。