这篇博文重点写了 CDQ\textbf{CDQ} 分治，整体分治
这是针对离线问题的很重要的处理方法

CDQ分治

CDQ

Acwing254

Acwing254

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#pragma GCC optimize(2)
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;

int n, m, maxy = -inf;
int ans[maxn];

class Node {
public:
    int x, y;
    int tp;

    Node() {}
    Node(int x, int y, int tp) : x(x), y(y), tp(tp) {}

    bool operator< (const Node& rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
} a[maxn], buf[maxn];

// == fenwick definition ==
class Fwick {
public:
    int C[maxn];
    int n;

    void _init(int n) {
        Set(C, -inf);
        this->n = n;
    }

    void add(int y, int val) {
        for(; y < n; y += lowbit(y)) C[y] = max(C[y], val);
    }

    int ask(int y) {
        int ret = -inf;
        for(; y > 0; y -= lowbit(y)) ret = max(ret, C[y]);

        return ret;
    }

    void reset(int y) {
        for(; y < n; y += lowbit(y)) C[y] = -inf;
    }
} fwick;
// == fenwick finished ==

// == CDQ ==
inline void work(int st, int ed, int w, int dx, int dy) {
    for(int i = st; i != ed; i += w) {
        int num = dx * buf[i].x + dy * buf[i].y;

        int y = dy == -1 ? maxy - buf[i].y : buf[i].y;

        if(a[buf[i].tp].tp == 1) fwick.add(y, num);
        else ans[buf[i].tp] = min(ans[buf[i].tp], abs(num - fwick.ask(y)));

        //debug(ans[buf[i].tp]);
    }

    for(int i = st; i != ed; i += w) {
        int y = dy == -1 ? maxy - buf[i].y : buf[i].y;
        if(a[buf[i].tp].tp == 1) fwick.reset(y);
    }
}

void CDQ(int l, int r) {
    int mid = (l + r) >> 1;
    if(l < mid) CDQ(l, mid);
    if(mid + 1 < r) CDQ(mid + 1, r);

    int tot = 0;
    _rep(i, l, r) {
        if((i <= mid && a[i].tp == 1) || (i > mid && a[i].tp == 2)) {
            buf[++tot] = a[i];
            buf[tot].tp = i;
        }
    }

    sort(buf + 1, buf + 1 + tot);
    work(1, tot + 1, 1, 1, 1);
    work(1, tot + 1, 1, 1, -1);
    work(tot, 0, -1, -1, 1);
    work(tot, 0, -1, -1, -1);
}
// == CDQ finished ==

void init() {
    Set(ans, inf);

    fwick._init(maxy);
}


int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    // get data
    _rep(i, 1, n) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].tp = 1;
        maxy = max(maxy, a[i].y);
    }
    _rep(i, 1, m) {
        scanf("%d%d%d", &a[n+i].tp, &a[n+i].x, &a[n+i].y);
        maxy = max(maxy, a[n+i].y);
    }
    maxy++;
    //debug(maxy);

    // get data finished
    init();
    CDQ(1, n + m);

    _rep(i, 1, n + m) if(a[i].tp == 2) printf("%d\n", ans[i]);
}

值域的整体二分

merge01
merge02
merge03

POJ2104

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
const int maxn = 1e5 + 10;
const int inf = 1e9;
int N, M;
int n = 0, tot = 0;
int ans[maxn];

// == discrete ==
int a[maxn], b[maxn];

void discrete() {
    sort(b + 1, b + 1 + N);
    n = unique(b + 1, b + 1 + N) - b - 1;
    _rep(i, 1, N) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
}
// original: b[a[i]], a in [1, n]
// == discrete finished ==

class Qry {
public:
    int x, y, z;
    int op;
    Qry() {}
    Qry(int x, int y, int z) : x(x), y(y), z(z) {}
    Qry(int x, int y) : x(x), y(y) {}
} qry[maxn << 1], lqry[maxn << 1], rqry[maxn << 1];

class Fwick {
public:
    int C[maxn];
    int n;
    void _init(int n) {
        this->n = n;
        memset(C, 0, sizeof(C));
    }

    void add(int x, int y) {
        for(; x <= n; x += lowbit(x)) C[x] += y;
    }

    int ask(int x) {
        int ret = 0;
        for(; x; x -= lowbit(x)) ret += C[x];
        return ret;
    }
} fwick;

void solve(int lval, int rval, int st, int ed) {
    if(st > ed) return;
    if(lval == rval) {
        _rep(i, st, ed) {
            if(qry[i].op > 0) ans[qry[i].op] = b[lval];
        }
        return;
    }

    int mid = (lval + rval) >> 1;

    int lt = 0, rt = 0;
    _rep(i, st, ed) {
        if(qry[i].op == 0) {
            // x -> y
            if(qry[i].y <= mid) {
                fwick.add(qry[i].x, 1);
                lqry[++lt] = qry[i];
            }
            else rqry[++rt] = qry[i];
        }
        else {
            int cnt = fwick.ask(qry[i].y) - fwick.ask(qry[i].x - 1);
            if(cnt >= qry[i].z) lqry[++lt] = qry[i];
            else {
                qry[i].z -= cnt;
                rqry[++rt] = qry[i];
            }
        }
    }

    _rep(i, st, ed) {
        if(qry[i].op == 0 && qry[i].y <= mid) fwick.add(qry[i].x, -1);
    }

    _rep(i, 1, lt) qry[st + i - 1] = lqry[i];
    _rep(i, 1, rt) qry[st + lt + i - 1] = rqry[i];

    solve(lval, mid, st, st + lt - 1);
    solve(mid + 1, rval, st + lt, ed);
}

void init() {
    n = 0;
    tot = 0;
    memset(ans, 0, sizeof(ans));
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    init();

    // == get data ==
    _rep(i, 1, N) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    discrete();
    // == get data finished ==

    // == get query ==
    _rep(i, 1, N) {
        qry[++tot] = Qry(i, a[i]);
        qry[tot].op = 0;
    }

    _rep(i, 1, M) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        qry[++tot] = Qry(l, r, k);
        qry[tot].op = i;
    }
    // == query finished ==

    // then solve the problem
    fwick._init(n + 1);
    solve(1, n, 1, tot);

    _rep(i, 1, M) printf("%d\n", ans[i]);
}

带修改的整体二分

algorithm\textbf{algorithm}
把 Ax 变成 y\textbf{把} \ A_x \ \text{变成} \ y

⟹{在 x 位置去掉一个值为 Ax 的数op=−1在 x 位置上增加一个值为 y 的数op=0\Longrightarrow \begin{cases} \text{在 } x \text{ 位置去掉一个值为 }A_x \text{ 的数} && op = -1\\ \text{在 } x \text{ 位置上增加一个值为 } y \text{ 的数} && op = 0 \end{cases}

查询操作 op=i∈[1,M]\text{查询操作 } op = i \in [1, M]

for ∀qryi∉[query cmd]\textbf{for} \ \forall qry_i \not\in [\textbf{query} \ \textbf{cmd}]
      ~~~~~~add(qry.x,qry.z)add(qry.x, qry.z)

{qry.z=−1if op=−1qry.z=1if op=0\begin{cases} qry.z=-1 && \textbf{if} \ op=-1 \\ qry.z=1 && \textbf{if} \ op = 0 \end{cases}

其他操作和整体二分大同小异
值得注意的是，整体二分中
A[i]⇒fwick.add(i,1)A[i] \Rightarrow \text{fwick.add}(i, 1)，而不是
fwick.add(A[i], 1)

我们要统计的是 Ai[⋯ ]⩽midA_i[\cdots] \leqslant mid 的数的个数
用 Ai⩽midA_i \leqslant mid 作为限制条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
const int maxn = 1e5 + 10;
const int inf = 1e9;
int N, M;
int n = 0, tot = 0, qt = 0;
int a[maxn], ans[maxn];

class Qry {
public:
    int x, y, z;
    int op;

    Qry() {}
    Qry(int x, int y, int z) : x(x), y(y), z(z) {}
    Qry(int x, int y) : x(x), y(y) {}

} qry[maxn * 3], lqry[maxn * 3], rqry[maxn * 3];

class Fwick {
public:
    int C[maxn];
    int n;

    void _init(int n) {
        this->n = n;
        memset(C, 0, sizeof(C));
    }

    void add(int x, int y) {
        for(; x <= n; x += lowbit(x)) C[x] += y;
    }

    int ask(int x) {
        int ret = 0;
        for(; x; x -= lowbit(x)) ret += C[x];
        return ret;
    }
} fwick;

void solve(int lval, int rval, int st, int ed) {
    if(st > ed) return;
    if(lval == rval) {
        _rep(i, st, ed) if(qry[i].op > 0) {
            ans[qry[i].op] = lval;
        }
        return;
    }

    int mid = (lval + rval) >> 1;

    int lt = 0, rt = 0;
    _rep(i, st, ed) {
        if(qry[i].op <= 0) {
            if(qry[i].y <= mid) {
                fwick.add(qry[i].x, qry[i].z);
                lqry[++lt] = qry[i];
            }
            else rqry[++rt] = qry[i];
        }
        else {
            int cnt = fwick.ask(qry[i].y) - fwick.ask(qry[i].x - 1);
            if(cnt >= qry[i].z) lqry[++lt] = qry[i];
            else {
                qry[i].z -= cnt;
                rqry[++rt] = qry[i];
            }
        }
    }

    _rep(i, st, ed) {
        if(qry[i].op <= 0 && qry[i].y <= mid) fwick.add(qry[i].x, -qry[i].z);
    }

    _rep(i, 1, lt) qry[st + i - 1] = lqry[i];
    _rep(i, 1, rt) qry[st + lt + i - 1] = rqry[i];
    solve(lval, mid, st, st + lt - 1);
    solve(mid + 1, rval, st + lt, ed);
}


void init() {
    n = 0;
    tot = 0;
    qt = 0;
    memset(ans, 0, sizeof(ans));
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    while (kase--) {
        init();

        scanf("%d%d", &N, &M);
        // get arr[]
        _rep(i, 1, N) {
            scanf("%d", &a[i]);
        }
        // arr[] finished
        // -> query[...]
        _rep(i, 1, N) {
            qry[++tot] = Qry(i, a[i]);
            qry[tot].op = 0;
            qry[tot].z = 1;
        }

        _rep(i, 1, M) {
            char cmd[2];
            scanf("%s", cmd);
            if(cmd[0] == 'Q') {
                int l, r, k;
                scanf("%d%d%d", &l, &r, &k);
                qry[++tot] = Qry(l, r, k);
                qry[tot].op = ++qt;
            }
            else {
                int x, y;
                scanf("%d%d", &x, &y);
                qry[++tot] = Qry(x, a[x]);
                qry[tot].z = -1;
                qry[tot].op = -1;

                qry[++tot] = Qry(x, y);
                qry[tot].z = 1;
                qry[tot].op = 0;
                a[x] = y;
            }
        }

        // then solve
        fwick._init(maxn + 1);
        solve(0, inf, 1, tot);

        _rep(i, 1, qt) printf("%d\n", ans[i]);
    }
}

整体二分实践

Meteors
Acwing268
Acwing268

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

// ============================================================== //

const int maxn = 3 * 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int K = 0;
vector<int> vec[maxn];

class BIU {
public:
    int id;
    ll val;
    BIU() {}
    BIU(int id, ll val) : id(id), val(val) {}
} P[maxn], pl[maxn], pr[maxn];

class Met {
public:
    int l, r;
    ll a;
    Met() {}
    Met(int l, int r, ll a) : l(l), r(r), a(a) {}
} A[maxn];

class Fwick {
public:
    ll C[maxn];
    int n;

    void _init(int n) {
        this->n = n;
        memset(C, 0, sizeof(C));
    }

    void add(int x, ll d) {
        for(; x <= m; x += lowbit(x)) C[x] += d;
    }

    ll ask(int x) {
        ll ret = 0;
        for(; x; x -= lowbit(x)) ret += C[x];
        return ret;
    }
} fwick;

void get(int k, int sgn) {
    ll val = sgn * A[k].a;

    if(A[k].l <= A[k].r) {
        fwick.add(A[k].l, val);
        fwick.add(A[k].r + 1, -val);
    }
    else {
        fwick.add(1, val);
        fwick.add(A[k].l, val);
        fwick.add(A[k].r + 1, -val);
    }
}

ll ans[maxn];

void solve(int lval, int rval, int st, int ed) {
    if(st > ed) return;
    if(lval == rval) {
        _rep(i, st, ed) ans[P[i].id] = lval;
        return;
    }

    int mid = (lval + rval) >> 1;
    int lt = 0, rt = 0;

    _rep(i, lval, mid) get(i, 1);
    _rep(i, st, ed) {
        // P[i].id is cur BIU
        ll tot = 0;
        for(auto x : vec[P[i].id]) {
            tot += fwick.ask(x);
            if(tot > P[i].val) break;
        }

        if(tot >= P[i].val) pl[++lt] = P[i];
        else {
            P[i].val -= tot;
            pr[++rt] = P[i];
        }
    }

    _rep(i, lval, mid) get(i, -1);

    _rep(i, 1, lt) P[st + i - 1] = pl[i];
    _rep(i, 1, rt) P[st + lt + i - 1] = pr[i];

    solve(lval, mid, st, st + lt - 1);
    solve(mid + 1, rval, st + lt, ed);
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    init();
    // get data
    _rep(i, 1, m) {
        int o;
        scanf("%d", &o);
        vec[o].push_back(i);
    }
    _rep(i, 1, n) {
        P[i].id = i;
        scanf("%lld", &P[i].val);
    }
    scanf("%d", &K);
    _rep(i, 1, K) {
        int l, r;
        ll a;
        scanf("%d%d%lld", &l, &r, &a);
        A[i] = Met(l, r, a);
    }
    A[++K] = Met(1, m, inf);

    // then solve the problem
    fwick._init(maxn);

    solve(1, K, 1, n);

    _rep(i, 1, n) ans[i] == K ? puts("NIE") : printf("%lld\n", ans[i]);
}