【题目链接】:http://hihocoder.com/problemset/problem/1483

【题意】



中文题

【题解】



二分最后的答案;

二分的时候;

对于每一个枚举的值x;

计算小于等于它的值(对应了若干个区间,且这些区间里面,每一个区间的价值(相同对数)都小于等于x)的区间个数ju;

如果ju>=k,则可以再变小一点,同时先记录ans=mid,否则数字变大一点;

计算小于等于x的区间个数;

可以用尺取法;

如果

l..r这个区间的值是符合要求的即区间价值≤x;

则

l+1..r

l+2..r

l+3..r

…

r..r

这r-l+1个区间肯定也是符合的;

然后右端点往右走;

新增加的区间价值,可以通过新增加的数字是什么,然后看看前面有多少个数字和它一样,通过O(1)算出来新的区间价值;

然后如果区间价值大于x了,则递增左端点;改变减少的数字的个数;减小区间价值;balabala



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define rep1(i,x,y) for (int i = x;i <= y;i++)

#define LL long long

const int N = 2e5+100;

LL k,tot,a[N];

int num[N],n;

map <int,int> dic;

LL ju(LL x)

{

    LL cur = 0,xyx = 0;

    rep1(i,1,tot) a[i] = 0;

    int l = 1;

    rep1(i,1,n)

    {

        cur += a[num[i]];

        a[num[i]]++;

        while (cur>x)

        {

            a[num[l]]--;

            cur-=a[num[l]];

            l++;

        }

        xyx+=i-l+1;

    }

    return xyx;

}

int main()

{

    //freopen("D:\\rush.txt","r",stdin);

    int T;

    cin >> T;

    while (T--)

    {

        dic.clear();

        tot = 0;

        cin >> n >> k;

        rep1(i,1,n)

        {

            int x;

            cin >> x;

            if (dic.find(x)==dic.end()) dic[x]=++tot;

            num[i] = dic[x];

        }

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

        while (l <= r)

        {

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

            if (ju(m)>=k)

            {

                ans = m;

                r = m-1;

            }

            else

                l = m+1;

        }

        cout << ans << endl;

    }

    return 0;

}