原题大意
给定n个数A1…An，小Ho想了解AL..AR中有多少对元素值相同。小Ho把这个数目定义为区间[L,R]的价值，用v[L,R]表示。
例如1 1 1 2 2这五个数所组成的区间的价值为4。
现在小Ho想知道在所有的的v[L,R] (1 <= L <= R <= n)中，第k小的值是多少。
输入：
2
4 7
1 1 2 3
3 6
100 100 100
输出：
0
3
算法分析
因为比较数字之间是否相同，所以与数字大小没有关系，先通过离散化将数据规模压缩，然后又因为最大的价值为 n*(n+1)/2，最小价值为 0，所以通过二分枚举价值，看是否有k个区间满足，然后通过区间的移动（尺取法），找到满足的解。
程序代码
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 200000+5;
ll n, k, a[maxn];
ll tot;
map<ll, ll> dict;
bool solve(ll x){
ll l = 0, num[tot],sum = 0, rk = 0;
for(ll i = 0; i < tot; i++)
num[i] = 0;//num记录当前区间内i的个数
//移动区间,尺取法
for(ll i = 0; i < n; i++)
{
sum += num[a[i]];//加上原有的值
num[a[i]]++;//因为多了一个，所以值加一
while(sum > x)//使得sum <= x的区间
{
sum -= --num[a[l++]];//l++，因为枚举的是i，所以左边界向右移动
//--num是因为抛弃左边界时，要减去它的值
}
rk += i-l+1;//因为最左边是l，如果l成立，那么t（l~i）到i的价值也一定满足。
}
return rk >= k;
}
int main(){
int T;
scanf("%d", &T);
while(T--)
{
dict.clear();
scanf("%lld%lld", &n, &k);
tot = 0;
for(int i = 0; i < n; i++){
scanf("%lld", &a[i]);
if(!dict.count(a[i])) dict[a[i]] = tot++;//离散化
a[i] = dict[a[i]];
}
ll l = 0, r = n * (n + 1) / 2 ,mid;
while(l <= r){
mid = (l + r) >> 1;
if(solve(mid))
r = mid - 1;
else
l = mid + 1;
}
printf("%lld\n", l);
}
return 0;
}