hihocoder-1483区间价值 (二分+尺取法)

题目链接：

区间价值

给定n个数A₁...A_n，小Ho想了解A_L..A_R中有多少对元素值相同。小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个数A₁…A_n(1<=A_i<=1,000,000,000)

Output

一个数表示答案。

Sample Input

2

4 7

1 1 2 3

3 6

100 100 100

Sample Output

0

3

题意：

思路：先离散化，然后二分答案，check的时候用尺取法取计算有多少个区间的价值<=mid，然后和k比较，复杂度为O(n*logn)

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn=2e5+10;

int a[maxn],n,vis[maxn],num[maxn],tep[maxn];

LL k;

int check(LL x)

{

    int l=1;

    LL sum=0,ans=0;

    for(int i=1;i<=n;i++)vis[a[i]]=0;

    for(int i=1;i<=n;i++)

    {

        sum=sum+vis[a[i]];

        vis[a[i]]++;

        while(sum>x&&l<=i)

        {

            vis[a[l]]--;

            sum-=vis[a[l]];

            l++;

        }

        ans=ans+(i-l+1);

    }

    if(ans>=k)return 1;

    return 0;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%lld",&n,&k);

        int cnt=0;

        for(int i=1;i<=n;i++)scanf("%d",&a[i]),tep[i]=a[i];

        sort(tep+1,tep+n+1);

        for(int i=1;i<=n;i++)

        {

            if(tep[i]==tep[i-1])continue;

            else num[cnt++]=tep[i];

        }

        for(int i=1;i<=n;i++)a[i]=lower_bound(num,num+cnt,a[i])-num;

        LL l=0,r=(LL)(n-1)*n/2;

        while(l<=r)

        {

            LL mid=(l+r)>>1;

            if(check(mid))r=mid-1;

            else l=mid+1;

        }

        cout<<r+1<<endl;

    }

    return 0;

}

巴特西

hihocoder-1483区间价值 (二分+尺取法)

区间价值

最新文章

热门文章