【CF840D】Destiny 分治(线段树)

时间：2025-02-14 16:33:55

【CF840D】Destiny

题意：给你一个长度为n的序列，q次询问，每次指定l r k，求[l,r]中出现次数$>\frac {r-l+1} k$的所有数中最小的那个数。

$n,q\le 3\times 10^5,a_i\le n,2\le k \le 5$

题解：考虑分治。对于每次询问，我们将整个序列分成[1,mid]和(mid,n]两部分，要么询问段与mid,mid+1有交点，要么询问段完全位于两边的某一段中，这种情况我们可以递归下去处理。

有一个显然的结论，就是我们将一个区间任意分成两部分，则出现次数最多的k个数要么是左面出现次数最多的k个数，要么是右面出现次数最多的k个数。

我们可以先预处理出：对于每个可能被分成的区间（其实就是线段树上的节点），它的mid往左延伸一些长度，对应的区间中出现次数最多个k个数。即区间[l,mid],[l+1,mid],[l+2,mid]...[mid,mid]的答案。这个从右往左扫一遍很容易得出。再预处理出[mid+1,mid+1],[mid+1,mid+2]...[mid+1,r]的答案。询问时直接拿出这两段区间，然后把2k个数都拿出来，全都在vector上二分一下统计真实的出现次数即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#define lson x<<1

#define rson x<<1|1

using namespace std;

const int maxn=300010;

int n,m,now,ans;

int cnt[maxn],tim[maxn],val[maxn];

struct node

{

	int v[5];

	int & operator [] (const int &a) {return v[a];}

}t;

vector<node> ls[maxn<<2],rs[maxn<<2];

vector<int> p[maxn];

bool cmp(const int &a,const int &b) {return (cnt[a]==cnt[b])?(a<b):(cnt[a]>cnt[b]);}

void build(int l,int r,int x)

{

	int i,j,mid=(l+r)>>1;

	now++;

	memset(t.v,0,sizeof(t.v));

	for(i=mid;i>=l;i--)

	{

		if(tim[val[i]]!=now)	tim[val[i]]=now,cnt[val[i]]=0;

		cnt[val[i]]++;

		for(j=0;j<5;j++)	if(t[j]==val[i])	break;

		if(j==5&&cmp(val[i],t[4]))	t[4]=val[i];

		for(j=4;j>0;j--)	if(cmp(t[j],t[j-1]))	swap(t[j-1],t[j]);

		ls[x].push_back(t);

	}

	now++;

	memset(t.v,0,sizeof(t.v));

	for(i=mid+1;i<=r;i++)

	{

		if(tim[val[i]]!=now)	tim[val[i]]=now,cnt[val[i]]=0;

		cnt[val[i]]++;

		for(j=0;j<5;j++)	if(t[j]==val[i])	break;

		if(j==5&&cmp(val[i],t[4]))	t[4]=val[i];

		for(j=4;j>0;j--)	if(cmp(t[j],t[j-1]))	swap(t[j-1],t[j]);

		rs[x].push_back(t);

	}

	if(l==r)	return ;

	build(l,mid,lson),build(mid+1,r,rson);

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

int main()

{

	//freopen("cf840D.in","r",stdin);

	n=rd(),m=rd();

	int i,j,a,b,c,l,r,mid,x;

	for(i=1;i<=n;i++)	val[i]=rd(),p[val[i]].push_back(i);

	build(1,n,1);

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

	{

		a=rd(),b=rd(),c=rd(),ans=1<<30;

		l=1,r=n,x=1;

		while(1)

		{

			mid=(l+r)>>1;

			if(a<=mid+1&&b>=mid)

			{

				now++;

				if(a<=mid)

				{

					t=ls[x][mid-a];

					for(j=0;j<c;j++)

					{

						if(tim[t[j]]!=now)	tim[t[j]]=now,cnt[t[j]]=0;

						if(c*(upper_bound(p[t[j]].begin(),p[t[j]].end(),b)-lower_bound(p[t[j]].begin(),p[t[j]].end(),a))>b-a+1)	ans=min(ans,t[j]);

					}

				}

				if(b>mid)

				{

					t=rs[x][b-mid-1];

					for(j=0;j<c;j++)

					{

						if(tim[t[j]]!=now)	tim[t[j]]=now,cnt[t[j]]=0;

						if(c*(upper_bound(p[t[j]].begin(),p[t[j]].end(),b)-lower_bound(p[t[j]].begin(),p[t[j]].end(),a))>b-a+1)	ans=min(ans,t[j]);

					}

				}

				break;

			}

			if(b<mid)	r=mid,x=lson;

			else	l=mid+1,x=rson;

		}

		if(ans==1<<30)	puts("-1");

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

	}

	return 0;

}//5 3 1 2 1 3 2 2 5 3 1 2 3 5 5 2

相关文章