區間價值 HihoCoder - 1483

給定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小的值是多少。

Input

第一行一個數T(T<=10)，表示資料組數。

對于每一組資料：

第一行兩個數n，k（1<=n<=200,000,1<=k<=n*(n+1)/2）

第二行n個數A1…An(1<=Ai<=1,000,000,000)

Output

一個數表示答案。

Sample Input

2
4 7
1 1 2 3
3 6
100 100 100      

Sample Output

0
3      

思路：我們仔細考慮，可以發現一個價值與區間個數的單調性。區間越短，價值越小，這樣的區間個數就越少。

然後統計小于等于目前二分的mid值的區間個數。跟k比較。如果大于等于k high = mid - 1，否則low = mid + 1.

統計區間個數的時候。要用一個比較巧的方法就是用一個雙指針。枚舉左端點，找到右端點。目前區間[l,r]符合條件那麼[l+1,r]...[r,r]都符合條件。

具體的看一下代碼吧。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;
const int MAXN = 2e5+7;
long long a[MAXN],temp[MAXN];
int vis[MAXN];
int n;
long long k;
bool check(long long mid)
{
    int ed = 0;
    long long sum = 0,num = 0;
    memset(vis,0,sizeof vis);
    for(int i = 0 ; i < n ; ++i)
    {
        while(ed < n && sum + vis[a[ed]] <= mid)
        {
            sum += vis[a[ed]];
            vis[a[ed]]++;
            ed++;
        }
        num += ed - i;
        vis[a[i]]--;
        sum -= vis[a[i]];
    }
    return num >= k;
}


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%lld",&n,&k);
        for(int i = 0 ; i < n ; ++i)
        {
            scanf("%lld",&a[i]);
            temp[i] = a[i];
        }
        int cnt;
        sort(temp,temp+n);
        cnt = unique(temp,temp+n) - temp;
        for(int i = 0 ; i < n ; ++i)a[i] = lower_bound(temp,temp+cnt,a[i]) - temp;
        long long low = 0, high = n*(n-1LL)/2;
        long long ans,mid;
        while(low <= high)
        {
            mid = (low + high)>>1LL;
            if(check(mid))
            {
                ans = mid;
                high = mid -1;
            }
            else low = mid + 1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}