基准时间限制：1 秒 空间限制：131072 KB 

 

第一行两个数n和k(1<=n<=100000,k<=n*(n-1)/2)

第二行n个数，0<=每个数<2^31

一个数表示答案。

 

Input示例

4 2

1 2 3 2

 

Output示例

2

题意：

思路：

先把数组都离散为[1,n]的数,注意相等的;
再二分答案t,check区间众数大于等于t的区间有多少个;(可以设区间众数大于等于t的区间为合法区间)
check的时候采用尺取法,按顺序枚举每个区间的左端点i,然后找到区间右端点的最小值;以这个左端点为合法区间的方案数为n-(r-1);
复杂度为O(nlogn)

AC代码：

//#include <bits/stdc++.h>

#include <vector>

#include <iostream>

#include <queue>

#include <cmath>

#include <map>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

#define Riep(n) for(int i=1;i<=n;i++)

#define Riop(n) for(int i=0;i<n;i++)

#define Rjep(n) for(int j=1;j<=n;j++)

#define Rjop(n) for(int j=0;j<n;j++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef long long LL;

template<class T> void read(T&num) {

    char CH; bool F=false;

    for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());

    for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());

    F && (num=-num);

}

int stk[], tp;

template<class T> inline void print(T p) {

    if(!p) { puts(""); return; }

    while(p) stk[++ tp] = p%, p/=;

    while(tp) putchar(stk[tp--] + '');

    putchar('\n');

}

const LL mod=1e9+;

const double PI=acos(-1.0);

const LL inf=1e10;

const int N=1e5+;

int n,k;

int a[N],flag[N];

struct node

{

    int a,id,ans;

}po[N];

int cmp(node x,node y)

{

    if(x.a==y.a)return x.id<y.id;

    return x.a<y.a;

}

int cmp1(node x,node y)

{

    return x.id<y.id;

}

int check(int x)

{

    mst(flag,);

    LL ans=;

    int num=;

    int r=;

    Riep(n)

    {

        while()

        {

            int pos=po[r].ans;

          if(pos!=-) if(flag[pos]>=x||r>n)break;

            r++;

            pos=po[r].ans;

            flag[pos]++;

        }

        ans=ans+n-(r-);

        flag[po[i].ans]--;

    }

    if(ans>=k)return ;

    return ;

}

int main()

{

    read(n);read(k);

    Riep(n)read(po[i].a),po[i].id=i;

    sort(po+,po+n+,cmp);

    po[].ans=po[].a=-;

    Riep(n)

    {

        if(po[i].a!=po[i-].a)po[i].ans=i;

        else po[i].ans=po[i-].ans;

    }

    sort(po+,po+n+,cmp1);

    int l=,r=n;

    while(l<=r)

    {

        int mid=(l+r)>>;

        if(check(mid))l=mid+;

        else r=mid-;

    }

    print(l-);

    return ;

}