把这两个东西放在一起讲是因为思想很相同。
所谓分治就是把问题分而治之（？）
整体二分和按时间分治其实本质上差不多，核心思想就是：把问题划分为左右两部分，只要在划分的过程中统计完左部分对右部分的贡献，接下来在分开处理左右两部分的时候就不会受另一半的影响。
先讲按时间分治（cdq分治）
按时间分治可以用cdq分治来解决。
cdq分治采用归并排序的思想，对于一个操作序列，保证它一开始按照时间有序。
然后我们可以通过统计左边操作对右边操作的影响，使得右边操作序列只关于自身有关，接下来只要分别处理左右两边的序列即可。
cdq分治可以用于处理高维偏序
对于偏序类问题，
一维排序，二维数据结构，三维分治，四维分治，高维暴力。
如何解决呢？
首先按照第一维排序，消除第一维影响
然后进行cdq分治，先递归处理左半边和右半边，
然后合并左右两边，按照第二维递增顺序，
由于右边已经处理完了，仅需考虑左边对右边询问的影响。
现在第一维和第二维都有序，只需要把左边的操作的第三维加入数据结构（通常是树状数组add(z, 1)）进行维护即可。
1 #include <bits/stdc++.h> 2 #define int int 3 #define Mid ((l + r) >> 1) 4 #define lson (rt << 1) 5 #define rson (rt << 1 | 1) 6 using namespace std; 7 int read(){ 8 char c; int num, f = 1; 9 while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; 10 while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';; 11 return f * num; 12 } 13 const int N = 1e6 + 1009; 14 struct node{ 15 int x, y, z, id, cnt; 16 }a[N], tmp[N]; 17 bool operator ==(const node &a, const node &b) { 18 return a.x == b.x && a.y == b.y && a.z == b.z; 19 } 20 int n, m, tot, ans[N], tt[N], tree[N]; 21 int ttt[N]; 22 bool cmp(node a, node b) { 23 if(a.x == b.x && a.y == b.y) return a.z < b.z; 24 if(a.x == b.x) return a.y < b.y; 25 return a.x < b.x; 26 } 27 void add(int x, int y) { 28 for( ; x <= m; x += x & -x) 29 tree[x] += y; 30 } 31 int query(int x) { 32 int ans = 0; 33 for( ; x; x -= x & -x) 34 ans += tree[x]; 35 return ans; 36 } 37 void cdq(int l, int r) { 38 if(l == r) return ; 39 cdq(l, Mid); cdq(Mid + 1, r); 40 int i = l, j = Mid + 1, now = l - 1; 41 while(i <= Mid && j <= r) { 42 if(a[i].y <= a[j].y) { 43 tmp[++now] = a[i]; 44 add(a[i].z, a[i].cnt); 45 i++; 46 } else { 47 tmp[++now] = a[j]; 48 ans[a[j].id] += query(a[j].z); 49 j++; 50 } 51 } 52 while(i <= Mid) { 53 tmp[++now] = a[i]; 54 add(a[i].z, a[i].cnt); 55 i++; 56 } 57 while(j <= r) { 58 tmp[++now] = a[j]; 59 ans[a[j].id] += query(a[j].z); 60 j++; 61 } 62 for(int i = l; i <= Mid; i++) add(a[i].z, -a[i].cnt); 63 for(int i = l; i <= r; i++) a[i] = tmp[i]; 64 } 65 main() 66 { 67 n = read(); m = read(); 68 for(int i = 1; i <= n; i++) { 69 a[i].x = read(); 70 a[i].y = read(); 71 a[i].z = read(); 72 a[i].cnt = 1; 73 } 74 sort(a + 1, a + 1 + n, cmp); 75 for(int i = 1; i <= n; i++) { 76 if(i == 1 || !(a[i] == a[i - 1])){ 77 a[++tot] = a[i]; 78 }else a[tot].cnt += a[i].cnt; 79 } 80 for(int i = 1; i <= tot; i++) a[i].id = i, ttt[i] = a[i].cnt; 81 cdq(1, tot); 82 for(int i = 1; i <= tot; i++) tt[ans[i] + ttt[i] - 1] += ttt[i]; 83 for(int i = 0; i < n; i++) printf("%d ", tt[i]); 84 return 0; 85 } 86 87 /* 88 10 3 89 3 3 3 90 2 3 3 91 2 3 1 92 3 1 1 93 3 1 2 94 1 3 1 95 1 1 2 96 1 2 2 97 1 3 2 98 1 2 1 99 三维偏序 100 先按照第一维排序 101 然后对第二维归并 102 归并时计算左对右的贡献 103 先双指针，满足当前统计出的第二维都有序 104 维护一个树状数组 105 */
然后是整体二分
整体二分引入了一个值域维度作为划分区间的标准，一个作用是动态求解区间k小/大值。
在二分的过程中，我们无法直接知道一个询问的答案，但是可以直接知道哪些操作不是询问的答案。
对于修改操作，可以拆分成减去原数再加上现在的数。
二分过程就是对当前的值域进行划分，对于小于等于当前中点的修改操作，我们将其加入数据结构（维护它对[l,r]的一个贡献）。
对于一个询问，我们只需要查询它区间内操作对他的贡献是否大于它所求的k大。
如果大于，说明答案在左半边。
否则，消除左半边对他的影响后加入右半边。
例题：
#include <iostream> #include <cstdio> #define int long long #define Mid ((l + r) >> 1) #define lson (rt << 1) #define rson (rt << 1 | 1) using namespace std; int read(){ char c; int num, f = 1; while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';; return f * num; } const int N = 5e5 + 1009; const int INF = 1e9; struct node{ int id, l, r, k; }q[N], lq[N], rq[N]; int n, m, t, ans[N], tree[N]; void add(int x, int y) { for( ; x <= n; x += x & -x) tree[x] += y; } int query(int x) { int ans = 0; for( ; x; x -= x & -x) ans += tree[x]; return ans; } void solve(int l, int r, int st, int ed) { if(st > ed) return ; if(l == r) { for(int i = st; i <= ed; i++) if(q[i].id) ans[q[i].id] = l; return ; } int lt = 0, rt = 0; for(int i = st; i <= ed; i++) { if(q[i].id == 0) { if(q[i].r <= Mid) { lq[++lt] = q[i]; add(q[i].l, 1); } else rq[++rt] = q[i]; } else { int c = query(q[i].r) - query(q[i].l - 1); if(q[i].k <= c) lq[++lt] = q[i]; else q[i].k -= c, rq[++rt] = q[i]; } } for(int i = st; i <= ed; i++) if(q[i].id == 0 && q[i].r <= Mid) add(q[i].l, -1); for(int i = 1; i <= lt; i++) q[st + i - 1] = lq[i]; for(int i = 1; i <= rt; i++) q[st + lt + i - 1] = rq[i]; solve(l, Mid, st, st + lt - 1); solve(Mid + 1, r, st + lt, ed); } signed main() { n = read(); m = read(); for(int i = 1; i <= n; i++) { q[++t].id = 0; q[t].l = i; q[i].r = read(); } for(int i = 1; i <= m; i++) { q[++t].id = i; q[t].l = read(); q[t].r = read(); q[t].k = read(); } solve(-INF, INF, 1, t); for(int i = 1; i <= m; i++) printf("%d ", ans[i]); return 0; }
#include <iostream> #include <cstdio> #define int long long #define Mid ((l + r) >> 1) #define lson (rt << 1) #define rson (rt << 1 | 1) using namespace std; int read(){ char c; int num, f = 1; while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';; return f * num; } const int N = 5e5 + 1009; const int INF = 1e9; struct node{ int id, l, r, k, type; }q[N], lq[N], rq[N]; int n, m, t, ans[N], tree[N], a[N]; void add(int x, int y) { for( ; x <= n; x += x & -x) tree[x] += y; } int query(int x) { int ans = 0; for( ; x; x -= x & -x) ans += tree[x]; return ans; } void solve(int l, int r, int st, int ed) { if(st > ed) return ; if(l == r) { for(int i = st; i <= ed; i++) if(q[i].id) ans[q[i].id] = l; return ; } int lt = 0, rt = 0; for(int i = st; i <= ed; i++) { if(q[i].id == 0) { if(q[i].r <= Mid) { lq[++lt] = q[i]; add(q[i].l, q[i].type); } else rq[++rt] = q[i]; } else { int c = query(q[i].r) - query(q[i].l - 1); if(q[i].k <= c) lq[++lt] = q[i]; else q[i].k -= c, rq[++rt] = q[i]; } } for(int i = 1; i <= lt; i++) add(lq[i].l, -lq[i].type); for(int i = 1; i <= lt; i++) q[st + i - 1] = lq[i]; for(int i = 1; i <= rt; i++) q[st + lt + i - 1] = rq[i]; solve(l, Mid, st, st + lt - 1); solve(Mid + 1, r, st + lt, ed); } signed main() { int cnt = 0; n = read(); m = read(); for(int i = 1; i <= n; i++) { q[++t].id = 0; q[t].l = i; q[i].r = read(); q[i].type = 1; a[i] = q[i].r; } for(int i = 1; i <= m; i++) { char c; cin >> c; if(c == 'C') { int x, y; x = read(); y = read(); q[++t].id = 0; q[t].l = x; q[t].r = a[x]; q[t].type = -1; q[++t].id = 0; q[t].l = x; q[t].r = y; q[t].type = 1; a[x] = y; } else { q[++t].id = ++cnt; q[t].l = read(); q[t].r = read(); q[t].k = read(); } } solve(-INF, INF, 1, t); for(int i = 1; i <= cnt; i++) printf("%lld ", ans[i]); return 0; }
1 #include <bits/stdc++.h> 2 #define int long long 3 #define Mid ((l + r) >> 1) 4 #define lson (rt << 1) 5 #define rson (rt << 1 | 1) 6 using namespace std; 7 int read(){ 8 char c; int num, f = 1; 9 while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; 10 while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; 11 return f * num; 12 } 13 const int N = 2e5 + 1009; 14 const int inf = 0x3f3f3f3f; 15 struct node { 16 int l, r, x, id; 17 } q[N], lq[N], rq[N]; 18 int n, m, ans[N], cnt; 19 int tree[N], tag[N]; 20 void update(int rt) { 21 tree[rt] = tree[lson] + tree[rson]; 22 } 23 void pushdown(int l, int r, int rt) { 24 if(!tag[rt]) return ; 25 tree[lson] += (Mid - l + 1) * tag[rt]; tag[lson] += tag[rt]; 26 tree[rson] += (r - (Mid + 1) + 1) * tag[rt]; tag[rson] += tag[rt]; 27 tag[rt] = 0; 28 } 29 void modify(int l, int r, int L, int R, int x, int rt) { 30 if(L <= l && r <= R) { 31 tree[rt] += x * (r - l + 1); 32 tag[rt] += x; 33 return ; 34 } 35 pushdown(l, r, rt); 36 if(L <= Mid) modify(l, Mid, L, R, x, lson); 37 if(Mid < R) modify(Mid + 1, r, L, R, x, rson); 38 update(rt); 39 } 40 int query(int l, int r, int L, int R, int rt) { 41 if(L <= l && r <= R) return tree[rt]; 42 pushdown(l, r, rt); 43 int ans = 0; 44 if(L <= Mid) ans += query(l, Mid, L, R, lson); 45 if(Mid < R) ans += query(Mid + 1, r, L, R, rson); 46 return ans; 47 } 48 void solve(int lval, int rval, int l, int r) { 49 if(l > r || lval > rval) return ; 50 if(lval == rval) { 51 for(int i = l; i <= r; i++) 52 if(q[i].id) 53 ans[q[i].id] = lval; 54 return ; 55 } 56 int mid = (lval + rval) / 2, lcnt = 0, rcnt = 0, fl = 0, fr = 0; 57 for(int i = l; i <= r; i++) { 58 if(q[i].id == 0) { 59 if(q[i].x > mid) { 60 modify(1, n, q[i].l, q[i].r, 1, 1); 61 lq[++lcnt] = q[i]; 62 } else rq[++rcnt] = q[i]; 63 } else { 64 int k = query(1, n, q[i].l, q[i].r, 1); 65 if(q[i].x <= k) lq[++lcnt] = q[i], fl = 1; 66 else q[i].x -= k, rq[++rcnt] = q[i], fr = 1; 67 } 68 } 69 for(int i = 1; i <= lcnt; i++) 70 if(lq[i].id == 0) 71 modify(1, n, lq[i].l, lq[i].r, -1, 1); 72 for(int i = 1; i <= lcnt; i++) q[l + i - 1] = lq[i]; 73 for(int i = 1; i <= rcnt; i++) q[l + lcnt + i - 1] = rq[i]; 74 if(fl) solve(mid + 1, rval, l, l + lcnt - 1); 75 if(fr) solve(lval, mid, l + lcnt, r); 76 } 77 signed main() 78 { 79 n = read(); m = read(); 80 for(int i = 1; i <= m; i++) { 81 int opt = read(), x, y, c; 82 x = read(); y = read(); c = read(); 83 if(opt == 1) 84 q[i] = (node){x, y, c, 0}; 85 else q[i] = (node) {x, y, c, ++cnt}; 86 } 87 solve(-inf, inf, 1, m); 88 for(int i = 1; i <= cnt; i++) 89 printf("%lld ", ans[i]); 90 return 0; 91 } 92 /* 93 整体二分？ 94 按照值域二分答案 95 96 */