CF840D Destiny

题目传送门。

题意简述：多次询问求出一个区间最小的出现次数严格大于 \(\frac{r-l+1}{k}\ (2\leq k\leq 5)\) 的最小的数。无解输出 \(-1\)。

注意到这个 \(k\) 很小，那么就要让正解尽量往上靠：设 \(d\) 为严格大于 \(\frac{r-l+1}{k}\) 的最小数。如果一个数 \(x\) 出现了 \(d\) 次，那么我们从小到大每隔 \(d-1\) 个数取出一个数（即取出第 \(1,1+d,1+2d,\cdots\) 小的数），\(x\) 必定出现在所有取出的数中。这个结论是显然的，因为如果 \(x\) 没有出现，那么 \(x\) 在整个区间的出现次数最多为 \(d-1\)。

这样就将题目转化为了区间 kth + 区间出现次数的主席树裸题。时间复杂度 \(\mathcal{O}(kn\log n)\)。

/*

	Powered by C++11.

	Author : Alex_Wei.

*/

#include <bits/stdc++.h>

using namespace std;

const int N=3e5+5;

int n,m,node,rt[N],val[N<<5],ls[N<<5],rs[N<<5];

void upd(int x){

	val[x]=val[ls[x]]+val[rs[x]];

}

void ins(int l,int r,int p,int &x,int pre){

	val[x=++node]=val[pre];

	if(l==r)return val[x]++,void();

	int m=l+r>>1;

	if(p<=m)ins(l,m,p,ls[x],ls[pre]),rs[x]=rs[pre];

	else ins(m+1,r,p,rs[x],rs[pre]),ls[x]=ls[pre];

	upd(x);

}

int query(int l,int r,int k,int x,int y){

	if(l==r)return l;

	int m=l+r>>1,sz=val[ls[y]]-val[ls[x]];

	if(sz<k)return query(m+1,r,k-sz,rs[x],rs[y]);

	return query(l,m,k,ls[x],ls[y]);

}

int check(int l,int r,int p,int x,int y){

	if(l==r)return val[y]-val[x];

	int m=l+r>>1;

	if(p<=m)return check(l,m,p,ls[x],ls[y]);

	return check(m+1,r,p,rs[x],rs[y]);

}

int main(){

	cin>>n>>m;

	for(int i=1;i<=n;i++)ins(1,n,read(),rt[i],rt[i-1]);

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

		int l=read(),r=read(),k=read();

		int rk=1,ans=-1,nd=(r-l+1)/k+1;

		while(rk<=r-l+1){

			int q=query(1,n,rk,rt[l-1],rt[r]);

			if(check(1,n,q,rt[l-1],rt[r])>=nd){

				ans=q;

				break;

			} rk+=nd;

		} printf("%d\n",ans);

	}

	return 0;

}

巴特西

CF840D Destiny

最新文章

热门文章