最近准备学数据结构乱搞，接下来学k-d tree
大致介绍
可以使用整体二分解决的题目需要满足以下性质：
1.询问的答案具有可二分性
2.修改对判定答案的贡献互相独立，修改之间互不影响效果
3.修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
4.贡献满足交换律，结合律，具有可加性
5.题目允许使用离线算法
——许昊然《浅谈数据结构题几个非经典解法》
感觉这段话得做了一些题目之后才能理解，直接看很抽象
后面做了题，对这个的理解加深了之后我再来补
目前的理解是：
把问题通过二分分成许多个子问题，每个子问题形如 \((l,r,Q)\)
其中 \(Q\) 表示 操作 的集合（而非只是询问），要求是，这些操作中，询问的答案值域位于 \([l,r]\) 之中，操作影响的值域也在 \([l,r]\) 之中（比如说，将 \(a_x \leftarrow y\) 这个操作影响的值域就跟 \(y\) 有关）。
对于操作，有三个要素：执行的顺序，下标范围，影响值域。
对于询问，也有两个要素：询问的下标范围，询问的答案范围。
例1
我们以这道题目解释的下标范围，值域范围两个要素。
区间查询第k小，可以参考主席树模板题二
我们先把数组原有的初始值抽象为在所有询问之前的修改操作
拿到一个操作集合 \(Q\) ，目前处理的值域范围 \([l,r]\)。
目前，我们的目标是把操作分为两个集合 \(Q_1,Q_2\) ，所对应值域分别为 \([l,mid],[mid+1,r]\)
先把所有影响 \(\le mid\) 的修改按下标插入到树状数组中。
树状数组中的区间查询解决了下标范围，而插入的修改影响 \(\le mid\) 解决了值域问题。
接下来对于某个查询 \([q.l,q.r,q.k]\)，询问 \([q.l,q.r]\) 中数的个数 \(tot\) 。
若 \(k > mid\) 那么 \(tot < k\) ，\(k \leftarrow k - tot\) 将这个询问归入 \(Q_2\)
否则 \(k \le mid\) 那么 \(tot \ge k\) ，归入 \(Q_1\)
接下来是代码实现
点击查看代码
int n , m , a[N] , ans[N] , b[N] , raw[N] , maxto;
unordered_map<int , int> to;
#define lowbit(x) (x & (-x))
int t[N];
void ch(int x , int v){
while(x <= n){
t[x] += v;
x += lowbit(x);
}
}
int qwq(int x){
int res = 0;
while(x > 0){
res += t[x];
x -= lowbit(x);
}
return res;
}
struct OP {
int op , id , l , r , k;
}q[N << 1] , q1[N << 1] , q2[N << 1];
int cnt;
void overall_binary(int l , int r , int L , int R){
if(L > R || l > r) return ;
if(l == r){
for(int i = L; i <= R; ++ i){
ans[q[i].id] = l;
}
return ;
}
int mid = ((l + r) >> 1) , cnt1 = 0 , cnt2 = 0;
for(int i = L; i <= R; ++ i){
if(q[i].op == 0){
if(q[i].k <= mid){
ch(q[i].l , 1);
q1[ ++ cnt1] = q[i];
}
else {
q2[ ++ cnt2] = q[i];
}
}
if(q[i].op == 1){
int tot = qwq(q[i].r) - qwq(q[i].l - 1);
if(q[i].k > tot){
q2[ ++ cnt2] = q[i];
q2[cnt2].k -= tot;
}
else {
q1[ ++ cnt1] = q[i];
}
}
}
/*CLEAR*/
for(int i = 1; i <= cnt1 && (!q1[i].op); ++ i){
ch(q1[i].l , -1);
}
/*MERGE*/
for(int i = 1; i <= cnt1; ++ i) q[L + i - 1] = q1[i];
for(int i = 1; i <= cnt2; ++ i) q[L + cnt1 + i - 1] = q2[i];
overall_binary(l , mid , L , cnt1 + L - 1);
overall_binary(mid + 1 , r , cnt1 + L , R);
}
signed main(){
n = read() , m = read();
for(int i = 1; i <= n; ++ i){
b[i] = a[i] = read();
}
sort(b + 1 , b + n + 1); b[0] = INF;
for(int i = 1; i <= n; ++ i){
if(b[i] != b[i - 1]){
++ maxto;
to[b[i]] = maxto;
raw[maxto] = b[i];
}
}
for(int i = 1; i <= n; ++ i){
a[i] = to[a[i]];
q[ ++ cnt] = {0 , 0 , i , 0 , a[i]};
}
for(int i = 1; i <= m; ++ i){
int l = read() , r = read() , k = read();
q[ ++ cnt] = {1 , i , l , r , k};
}
overall_binary(1 , maxto , 1 , cnt);
for(int i = 1; i <= m; ++ i){
writeln(raw[ans[i]]);
}
return 0;
}
例2
通过这道题，我们将解释修改的执行顺序
单点修改，区间查询第k小
大致上与上一题相同
单点修改我们把它改成先删除，在修改。（如果直接修改的话，之前树状数组里面的贡献没有减掉）
执行顺序直接跟据拿到的集合中的顺序就行了。
因为其他不在集合里的修改对这个集合里面的查询不会有影响，而因为拿到的集合是不断分裂的，一定有序（比如，cdq分治是从集合小到大处理，整体二分则不一样）。
这同时也解决了第2点的性质，如果修改之间互相有影响，那么对其他有影响的修改一定会在划分集合时被分到多个集合中，这样时间复杂度就没法保证了。
点击查看代码
int n , m , a[N] , ans[N] , b[N] , o , raw[N << 2] , maxto;
unordered_map<int , int> to;
#define lowbit(x) (x & (-x))
int t[N << 2];
void ch(int x , int v){
while(x <= maxto){
t[x] += v;
x += lowbit(x);
}
}
int qwq(int x){
int res = 0;
while(x > 0){
res += t[x];
x -= lowbit(x);
}
return res;
}
struct OP {
int op , id , l , r , k;
}q[N << 2] , q1[N << 2] , q2[N << 2];
int cnt;
void overall_binary(int l , int r , int L , int R){
if(L > R || l > r) return ;
if(l == r){
for(int i = L; i <= R; ++ i){
ans[q[i].id] = l;
}
return ;
}
int mid = ((l + r) >> 1) , cnt1 = 0 , cnt2 = 0;
for(int i = L; i <= R; ++ i){
if(q[i].op <= 0){
if(q[i].k <= mid){
ch(q[i].l , ((q[i].op == 0) ? 1 : -1));
q1[ ++ cnt1] = q[i];
}
else {
q2[ ++ cnt2] = q[i];
}
}
if(q[i].op == 1){
int tot = qwq(q[i].r) - qwq(q[i].l - 1);
if(q[i].k > tot){
q2[ ++ cnt2] = q[i];
q2[cnt2].k -= tot;
}
else {
q1[ ++ cnt1] = q[i];
}
}
}
/*CLEAR*/
for(int i = 1; i <= cnt1; ++ i){
if(q1[i].op <= 0)
ch(q1[i].l , ((q1[i].op == 0) ? -1 : 1));
}
/*MERGE*/
for(int i = 1; i <= cnt1; ++ i) q[L + i - 1] = q1[i];
for(int i = 1; i <= cnt2; ++ i) q[L + cnt1 + i - 1] = q2[i];
overall_binary(l , mid , L , cnt1 + L - 1);
overall_binary(mid + 1 , r , cnt1 + L , R);
}
signed main(){
n = read() , m = read();
for(int i = 1; i <= n; ++ i){
a[i] = read();
}
for(int i = 1; i <= n; ++ i){
q[ ++ cnt] = {0 , 0 , i , 0 , a[i]};
}
for(int i = 1; i <= m; ++ i){
char op = readc();
if(op == 'Q'){
int l = read() , r = read() , k = read();
q[ ++ cnt] = {1 , i , l , r , k};
}
if(op == 'C'){
int x = read() , y = read();
q[ ++ cnt] = {-1 , 0 , x , 0 , a[x]};
q[ ++ cnt] = {0 , 0 , x , 0 , y};
a[x] = y;
}
}
for(int i = 1; i <= cnt; ++ i){
if(q[i].op <= 0){
b[ ++ o] = q[i].k;
}
}
sort(b + 1 , b + o + 1);
b[0] = INF;
for(int i = 1; i <= o; ++ i){
if(b[i] != b[i - 1]){
++ maxto;
to[b[i]] = maxto;
raw[maxto] = b[i];
}
}
for(int i = 1; i <= cnt; ++ i){
if(q[i].op <= 0){
q[i].k = to[q[i].k];
}
// cout << q[i].op << " " << q[i].l << " ";
// cout << q[i].r << " " << q[i].id << " " << q[i].k << endl;
}
memset(ans , -1 , sizeof ans);
overall_binary(1 , maxto , 1 , cnt);
for(int i = 1; i <= m; ++ i){
if(ans[i] != -1) writeln(raw[ans[i]]);
}
return 0;
}
例3（构造单调性序列）
给定一个序列，每次操作可以把某个数 \(+1\) 或 \(-1\) 。要求把序列变成单调不降的，并且修改后的数列只能出现修改前的数，输出最小操作次数
这个可以看oiwiki上的，挺清晰的
点击查看代码
int n , a[N] , ans[N];
void overall_binary(int l , int r , int L , int R){
if(l > r || L > R) return ;
if(l == r){
for(int i = L; i <= R; ++ i){
ans[i] = l;
}
return ;
}
int mid = (l + r) >> 1;
ll sum = 0;
for(int i = L; i <= R; ++ i){
sum += abs(mid + 1 - a[i]);
}
int pos = L - 1;
ll minx = sum;
for(int i = L; i <= R; ++ i){
sum -= abs(mid + 1 - a[i]);
sum += abs(mid - a[i]);
if(sum < minx) pos = i , minx = sum;
}
overall_binary(l , mid , L , pos);
overall_binary(mid + 1 , r , pos + 1 , R);
}
signed main(){
n = read();
for(int i = 1; i <= n; ++ i){
a[i] = read();
}
overall_binary(-1e9 , 1e9 , 1 , n);
ll res = 0;
for(int i = 1; i <= n; ++ i){
res += abs(ans[i] - a[i]);
}
writeln(res);
return 0;
}