K-th Number 题解

Update:添加了一种常数小的做法

一.闲话

看了下大佬们的题解，然后。。。二分+尺取？？？

我：。。。

二.题解

题目简意:

数组b的元素是，数组a中所有区间长度大于等于k的区间的第k大数(有点绕？)

求数组b中第m大的数

要做这题，首先我们需要明白一个简单的性质，对于一个序列，我们如果添加进一个新数进去后，其中第k大数一定不会减小。

证明：

1.如果添加进去的数比原k大数大，那么，k大数改变，变成原k-1大的数（若k=1，就是添加进去的这个数）

2.如果添加进去的数小于等于原k大数，则排序后对前k大的数没任何影响，所以，k大数不变

知道了这个性质后，我们就可以开做了

直接枚举肯定很麻烦，所以我们考虑二分答案。

假设，我们二分出了一个x，那么，我们现在就需要判断的是，x和我们要求的b数组中第m大数的大小关系。

那么，我们就需要求，b数组中有多少个数大于等于x，即等价于，有多少个长度大于等于k的区间的第k大数比x大。

我们先枚举左端点l，那么，假设我们找到了一个右端点r，使得l-r的第k大数大于等于x，那么由我们之前得到的那个性质，就一定有：l-(r+1),l-(r+2)...l-n的第k大数都大于等于x

所以，我们对于每个左端点l，求出最小的满足区间第k大数大于等于x的右端点r即可，答案加上(n-r+1)

那么，很明显，这就又是一个二分问题了，我们就可以考虑：枚举左端点，二分右端点。

问题就又来了，我们如何找区间第k大数呢？

主席树了解下？

于是，我们就可以做出这道题了，复杂度高达

交一发，果然T了(并且百般卡常无效qwq)，那么，我们怎么优化呢？

还是利用那个性质，我们倒序枚举左端点，设上次的右端点答案为r，每次左端点移动后，kth一定不会减小，因为我们之前有(l+1)-r的第k大数大于等于x，那么同理就一定有l-r的第k大数大于等于x，那么，我们只需再继续判断l-(r-1)...的第k大数是否大于等于x即可，如果有一个小于了，那么这时的右端点加1就是我们的答案，r这个右端点我们可以使用单调指针维护，复杂度就优化到了优秀的了，可以通过此题。

PS:三年OI一场空，不开long long见祖宗

#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1;
struct zxs{
    int lson,rson,w;
}t[N<<5];
int sav[N];
int rt[N],cnt;
int a[N],b[N],s[N];
inline void insert(int pas,int &now,int l,int r,int x){
    now=++cnt;
    t[now]=t[pas];
    ++t[now].w;
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        insert(t[pas].lson,t[now].lson,l,mid,x);
    }else{
        insert(t[pas].rson,t[now].rson,mid+1,r,x);
    }
}
inline int kth(int pas,int now,int l,int r,int k){//因为求的第k大，所以左右区间要反过来写 
    if(l==r){
        return l;
    }
    int sum=t[t[now].rson].w-t[t[pas].rson].w,mid=(l+r)>>1;
    if(sum>=k){
        return kth(t[pas].rson,t[now].rson,mid+1,r,k);
    }
    return kth(t[pas].lson,t[now].lson,l,mid,k-sum);
}
int n,k,m,al;
inline int calc(int x){
    int ans=0,r=-1;//单调指针维护
    for(int i=n-k+1;i;--i){//枚举区间左端点
        if(sav[i]<x){//小剪枝
            continue;
        }
        if(r==-1){
            int L=i+k-1,R=n;
            while(L<=R){
                int mid=(L+R)>>1;
                if(kth(rt[i-1],rt[mid],1,al,k)>=x){
                    r=mid,R=mid-1;
                }else{
                    L=mid+1;
                }
            }
        }else{
            while((r-i+1)>k&&kth(rt[i-1],rt[r-1],1,al,k)>=x){
                --r;
            }
        }
        ans+=(n-r+1);
    }
    return ans;
}
inline int read(){
    char ch=getchar();int w=0,ss=0;
    while(ch<'0'||ch>'9')w|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')ss=(ss*10+(ch-'0')),ch=getchar();
    return w?-ss:ss;
}
signed main(){
    int T=read();
    while(T--){
        memset(rt,0,sizeof(rt));cnt=0;//清空主席树
        n=read(),k=read(),m=read();
        for(int i=1;i<=n;++i){
            a[i]=read();
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        al=unique(b+1,b+n+1)-b-1;
        for(int i=1;i<=n;++i){
            int x=a[i];
            a[i]=lower_bound(b+1,b+al+1,x)-b;
            s[a[i]]=x;
        }
        for(int i=1;i<=n;++i){
            insert(rt[i-1],rt[i],1,al,a[i]);
        }
        for(int i=n-k+1;i;--i){
            sav[i]=kth(rt[i-1],rt[n],1,al,k);
        }
        int l=1,r=al,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            int tot=calc(mid);//区间kth大于等于mid的有几个
            if(tot>=m){
                ans=mid;l=mid+1;
            }else{
                r=mid-1;
            }
        }
        printf("%lld\n",s[ans]);
    }
    return 0;
}

三.新增

关于此题，我们分析一下：
一个区间第k大的数不小于x的条件是什么？

答案就是一个区间内不小于x的数的个数不小于k

那么，我们就会发现，我们其实并不需要知道每个数的值，实际上对我们有用的只有每个数与x的大小关系，然后，我们就可以直接用贡献法计算。

我们把所有值不下于x的赋为1，剩下的赋为0，那么，二分求的东西就被转换成了：

有多少个区间的区间和不下于k，且序列里面的值只可能是0或1

然后随便搞个前缀和加个单调指针就行了

（其实可以不用单调指针直接用桶存的，常数更小，但是，由于脑袋有点晕，出锅了，就懒得改了）

代码：

#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1;
int a[N],b[N];
int n,k,m;
inline int calc(int x){
    for(int i=1;i<=n;++i){
        b[i]=(a[i]>=x);
        b[i]+=b[i-1];
    }
    int ans=0,l=1;
    for(int i=1;i<=n;++i){//枚举右端点
        while(b[i]-b[l-1]>=k)++l;
        ans+=(l-1);
    }
    return ans;
}
inline int read(){
    char ch=getchar();int w=0,ss=0;
    while(ch<'0'||ch>'9')w|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')ss=(ss*10+(ch-'0')),ch=getchar();
    return w?-ss:ss;
}
signed main(){
    int T=read();
    while(T--){
        n=read(),k=read(),m=read();
        for(int i=1;i<=n;++i){
            a[i]=read();
        }
        int l=1,r=1e9,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            int tot=calc(mid);//区间kth大于等于mid的有几个
            if(tot>=m){
                ans=mid;l=mid+1;
            }else{
                r=mid-1;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}