第一反应这个东西和cdq分治差不多
我们都会二分答案
整体二分就是把所有的询问一起二分答案
用一道题来说明吧
!(题目链接)[https://www.luogu.org/problemnew/show/P3834]
很明显这道题可以用主席树秒掉
但我们现在要用整体二分的角度来看它
预处理 ： 离散化
我们从单个询问（即二分答案 开始：
【大佬自动跳过
对于一个询问[x, y, k]
由于已经离散化 我们枚举答案的区间就是[1, n]
首先枚举mid = (1 + n) / 2;
我们仅考虑原数组小于等于mid的数
用一棵树状数组维护
即如果a[i] <= mid 那么 ins(i, 1); p.s ins(位置， 值);
这样的话query(y) - query(x - 1)就是询问区间内小于等于mid的数的个数
记这个个数为tmp
如果tmp < k那么mid需要大一些 l = mid + 1
如果tmp >= k那么mid需要小一些 r = mid
记得每次划分后清空树状数组
再p.s.下 x, y是询问区间始终不变
l, r, mid维护答案区间 每次规模缩小一半
如果有多个询问呢？
我们看看要做哪些改变
1.由于不可能每到一个答案区间都找一遍有哪些数小于等于mid
所以要把原数列看作空的 把值当作插入操作
这样就可以按照（（要插入的值）的大小）随答案区间被划分
因此 被划分到右区间的询问就要累加tmp
2.由于有多组询问
我们需要把他们按照上述单点询问的划分方式分成两组
其过程类似归并排序
好啦 上代码
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
//整体二分
const int N = 2e5 + 5;
struct Node{
int x, y, z, type, id, w;
}q[N << 1], ql[N << 1], qr[N << 1];//询问以及划分用的（类似归并排序
int a[N], b[N];//a[]原数列 b[]离散化用
int n, m;
long long c[N];//树状数组
int ans[N];//记录答案
int tmp[N << 1];
//记录当前答案区间q[i]的询问区间内有多少个小于等于mid的值
inline void ins(int x, int y){
for(int i = x; i < N; i += i & (-i)) c[i] += y;
}
inline int query(int x){
int ret = 0;
for(int i = x; i; i -= i & (-i)) ret += c[i];
return ret;
}
//树状数组
void solve(int x, int y, int l, int r){
if(x > y) return ;
if(l == r){
for(int i = x; i <= y; i++)
if(!q[i].type) ans[q[i].id] = b[l];
return ;
}
//已经找到单点啦 记录答案
int mid = l + ((r - l) >> 1);
for(int i = x; i <= y; i++){
if(q[i].type && q[i].x <= mid) ins(q[i].id, 1);
if(!q[i].type) tmp[i] = query(q[i].y) - query(q[i].x - 1);
}
for(int i = x; i <= y; i++)
if(q[i].type && q[i].x <= mid) ins(q[i].id, -1);
//计算tmp 别忘记清空树状数组哦
int c1 = 0, c2 = 0;
for(int i = x; i <= y; i++){
if(q[i].type){
if(q[i].x <= mid) ql[++c1] = q[i];
else qr[++c2] = q[i];
}//插入的划分
else if(tmp[i] + q[i].w >= q[i].z) ql[++c1] = q[i];
else {
q[i].w += tmp[i]; qr[++c2] = q[i];
}//后两种情况是询问的划分
}
//根据tmp划分到左右答案区间
for(int i = 1; i <= c1; i++) q[x + i - 1] = ql[i];
for(int i = 1; i <= c2; i++) q[x + c1 + i - 1] = qr[i];
//类似于归并排序逆操作
solve(x + c1, y, mid + 1, r);
solve(x, x + c1 - 1, l, mid);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b,
q[i] = (Node){a[i], 0, 0, 1, i, 0};
//输入并离散化 放入插入操作
for(int i = 1, l, r, k; i <= m; i++){
scanf("%d%d%d", &l, &r, &k);
q[i + n] = (Node){l, r, k, 0, i, 0};
}
//放入查询操作
solve(1, n + m, 1, n);
//整体二分
for(int i = 1; i <= m; i++) printf("%d
", ans[i]);
return 0;
}