题目链接

https://vjudge.net/problem/HihoCoder-1483

解题思路

二分第k小的值，假设为m，统计区间价值小于等于m的区间数量（这个统计的方法真是绝了），若数量比k大说明二分的区间右端点大了；反之，说明二分的区间左端点小了。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+100;
ll k,a[N],b[N],n,vis[N];
int T;
bool check(ll x){//统计区间价值小于等于x的区间数量，太牛逼了！！！！ 

    ll sum=0,num=0;
    memset(vis,0,sizeof vis);
    for(int l=1,r=1;l<=n;l++){
        for(;r<=n && sum+vis[b[r]]<=x;r++){
            sum+=vis[b[r]];//从区间右侧添加一个数字对整个区间价值的影响。在上一个区间的价值基础上加上与新添加数字相同的数字个数 
            vis[b[r]]++;//新添加的数字数量加1 
        }
        num+=r-l;//此时r指向sum<=x区间右端点的下一个 
        vis[b[l]]--;//左侧删除数字，类似于右侧添加新数字。注意先--，再统计。 
        sum-=vis[b[l]];
        if(num>=k) return 1;
    }
    return 0;

        //也可
    /*
    ll sum=0,num=0;
    memset(vis,0,sizeof vis);
    for(int i=1,j=1;i<=n;i++){
        sum+=vis[b[i]];
        vis[b[i]]++;
        while(j<=n && sum>x){
            vis[b[j]]--;
            sum-=vis[b[j]];
            j++;
        }
        num+=i-j+1;
        if(num>=k) return 1;
    }
    return 0;
    */
}
int main(){
    cin>>T;
    while(T--){
        memset(b,0,sizeof b);
        memset(a,0,sizeof a);
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
        //离散化
        sort(a+1,a+n+1);
        int cnt=unique(a+1,a+n+1)-a-1;
        for(int i=1;i<=n;i++)
        b[i]=lower_bound(a+1,a+cnt+1,b[i])-a; 

        ll L=0,R=n*(n-1)/2;//左右端点注意 
        while(L<=R){
            ll mid=(L+R)>>1;
            if(check(mid))R=mid-1;
            else L=mid+1; 
        }
        cout<<R+1<<endl;
    }
}