前言：

老火星人了

解析：

很妙的二分题。如果没想到二分答案。。

很容易想到尝试用双指针扫一下，看看能不能统计答案。

首先，tail指针右移时很好处理，因为tail指针右移对区间最大值的影响之可能作用在a[tail]上，因此只需要维护区间最大出现次数对应的值即可。

但是会发现，head指针右移时很难处理，因为如果原来区间最大值减小，使其不成为当前区间最大值时，这时无法快速找到新的区间最大值。（反正我不会，嘤）

这时应该怎么办呢？

考虑二分答案，可以很妙的消除掉这个影响。

我们考虑当前二分的答案是mid，要判断这个mid是否合法，只要计算有多少区间的众数出现次数小于mid即可。这个东西一看就很好维护。一个指针扫一遍就完了。

二分边界可能需要调一下。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=100000+10;

#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)

#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })

char buf[1 << 20], *p1, *p2;

int n;

ll k;

int a[maxn],b[maxn],buc[maxn];

bool cmp(int x,int y){

	return x<y;

}

bool check(int x){

	memset(buc,0,sizeof(buc));

	int head=0;

	ll res=0;

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

		buc[a[i-1]]--;

		while(head<=n&&buc[a[head+1]]+1<x){

			head++;

			buc[a[head]]++;

		}

		if(head>n) head--;

		res+=head-i+1;

	}

	return res>=k;

}

void Solve(){

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

	k=1ll*n*(n+1)/2-k+1;

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

		scanf("%d",&a[i]);

		b[i]=a[i];

	}

	sort(b+1,b+n+1,cmp);

	b[0]=unique(b+1,b+n+1)-b-1;

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

		a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;

		buc[a[i]]++;

	}

	int L=1,R=0;

	for(int i=1;i<=b[0];++i) R=max(R,buc[i]);

	while(L<=R){

		int mid=(L+R)>>1;

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

		else L=mid+1;

	}

	printf("%d\n",R);

}

int main(){

	freopen("C.in","r",stdin);

        freopen("C.out","w",stdout);

	Solve();

	return 0;

}

巴特西

[火星补锅] 非确定性有穷状态决策自动机练习题Vol.1 T3 第K大区间题解

前言：

解析：

最新文章

热门文章

巴特西

[火星补锅] 非确定性有穷状态决策自动机练习题Vol.1 T3 第K大区间 题解

前言：

解析：

最新文章

热门文章

[火星补锅] 非确定性有穷状态决策自动机练习题Vol.1 T3 第K大区间题解