1. 题目

传送门=￣ω￣=

2. 题解

这，，，是我写的第多少个区间 kth 问题的算法&代码了？？？

列举一下 QvQ：

• 分块
• 二分套线段树
• 主席树
• 二分套线段树套 splay（资磁修改）
• 整体二分

QvQ

痛苦不堪。

整体二分个人感觉就是二分答案の升级版。

一般的二分答案做这题的话，就是对于每个询问，二分一个答案，然后去线段树里查询这个答案的排名，在确定这个询问的答案是小于还是大于（或等于）这个二分出来的答案，最后得到准确答案。

而我们的整体二分则是先把所有询问&修改按输入顺序存好（初始序列视为 n 次修改），然后一起二分答案。

二分一个答案以后，我们可以把所有询问分为两部分：答案小于二分出来的答案的询问和大于二分出来的答案的询问。

至于修改操作，我们可以判断：如果这个修改的值是小于二分出来的答案的，就说明这个修改会影响询问的分类，我们就执行这些修改，等把询问分完类以后再修改回来。执行修改在这题中可以用树状数组维护！这个树状数组维护着每个区间内小于等于二分出来的答案的数字有多少个。

具体怎么分类呢？我们对于每个询问，都查询一下在这个询问的区间内，小于等于二分出来的答案的数字有多少个，如果小于等于二分出来的答案的数字个数是大于等于这个询问对应的 k 的，则说明这个询问的答案是小于等于二分出来的答案的，否则说明是大于二分出来的答案的。

于是我们就成功分好类啦！

然后在递归，整体二分两个分类的询问即可。

具体看代码吧，我也是看代码才看懂的，毕竟语言的表达还是赶不上直观的代码。

代码：

#include <bits/stdc++.h>
#define NS (100005)
#define MS (100005)
#define lowbit(a) (a&-a)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{int l,r,k,id,type;}Q[NS+MS],Q1[NS+MS],Q2[NS+MS];
//询问/修改的结构体，Q1 为第一个分类（小于等于二分出来的答案的），Q2 为第二个分类
int T,n,m,ans[MS],t[NS];//依次是数据组数，n，m，答案数组，树状数组
void add(int pos,int d){for(;pos<=n;pos+=lowbit(pos))t[pos]+=d;}//树状数组增减 pos 位置的值
int get_sum(int pos)//获取前 pos 个位置的值的和
{
    int tmp=0;
    for(;pos;pos-=lowbit(pos))tmp+=t[pos];
    return tmp;
}
void binary(int QL,int QR,int l,int r)//整体二分
{
    if(QL>QR)return;
    if(l==r){for(int i=QL;i<=QR;i++)if(Q[i].type)ans[Q[i].id]=l;return;}//二分到了精确地答案
    int mid=(l+r)>>1,x1=0,x2=0;
    //mid 是二分出来的答案，x1 是统计第一个分类的询问/修改个数，x2 是统计第二个分类的个数
    for(int i=QL,tmp;i<=QR;i++)
        if(Q[i].type)//如果是询问
        {
            tmp=get_sum(Q[i].r)-get_sum(Q[i].l-1);//看它对应的区间内小于等于 mid 的值有多少个
            if(Q[i].k<=tmp)Q1[++x1]=Q[i];//该询问答案是小于等于 mid 的，分到第一类
            else Q2[++x2]=Q[i],Q2[x2].k-=tmp;//分到第二类，记得询问的 k 要改变，类似于主席树
        }
        else if(Q[i].k<=mid)add(Q[i].id,1),Q1[++x1]=Q[i];//发现是小于等于 mid 的修改
        else Q2[++x2]=Q[i];//大于 mid 的修改
    for(int i=1;i<=x1;i++)if(!Q1[i].type)add(Q1[i].id,-1);//清空刚刚的修改免得影响后面的在整体二分
    for(int i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
    for(int i=1;i<=x2;i++)Q[QL+x1+i-1]=Q2[i];
    binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);//继续二分
}
int main()
{
    IN(T);
    while(T--)
    {
        IN(n),IN(m),memset(t,0,sizeof(t));
        for(int i=1;i<=n;i++)IN(Q[i].k),Q[i].id=i,Q[i].type=0;//将序列转化为修改操作
        for(int i=1+n;i<=m+n;i++)
            IN(Q[i].l),IN(Q[i].r),IN(Q[i].k),Q[i].id=i-n,Q[i].type=1;//询问操作输入
        binary(1,m+n,INT_MIN,INT_MAX);//求答
        for(int i=1;i<=m;i++)printf("%d\n",ans[i]);//输出答案
    }
    return 0;
}