P4168-蒲公英-分块

蒲公英

暴力分块思想。分块的思想与莫队相同。它能将时间和空间复杂度均摊XD

belong表示所属区块，num维护区间颜色出现次数，maxx维护区间max值。查询时只需要比较两端的区块即可。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<utility>

#include<cstring>

#include<cctype>

using namespace std;

inline int read(){

	int x=0,w=0;char c=getchar();

	while(!isdigit(c))w|=c=='-',c=getchar();

	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

	return w?-x:x;

}

typedef pair<int,int> pii;

namespace star

{

	const int maxn=40010,block=1500,maxm=50;

	int n,m,a[maxn],cnt,cn=1;

	int belong[maxn],beg[maxm],end[maxm],num[maxm][maxm][maxn],maxx[maxm][maxm];

	int ed[maxn],time=0;

	int color[maxn],id[maxn];

	int con[maxn];

	pii p[maxn];

	inline void solve(){

		int l=0,r=0,ans=0;

		while(m--){

			time++;

			l=(read()+ans-1)%n+1,r=(read()+ans-1)%n+1;

			if(l>r)swap(l,r);

			ans=0;

			int mx=0,mxid=0;

			if(belong[l]==belong[r]){

				for(int i=l;i<=r;i++)

				{

					if(ed[id[i]]!=time)con[id[i]]=0,ed[id[i]]=time;

					con[id[i]]++;

					if(con[id[i]]>mx or (con[id[i]]==mx and id[i]<mxid))mxid=id[i],mx=con[mxid];

				}

				ans=color[mxid];

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

			}else{

				int L=belong[l]+1,R=belong[r]-1;

				mxid=maxx[L][R];mx=num[L][R][mxid];

				for(int i=l;i<beg[L];i++)

				{

					if(ed[id[i]]!=time)con[id[i]]=0,ed[id[i]]=time;

					con[id[i]]++;

					if(con[id[i]]+num[L][R][id[i]]>mx or (con[id[i]]+num[L][R][id[i]]==mx and id[i]<mxid))mxid=id[i],mx=con[mxid]+num[L][R][id[i]];

				}

				for(int i=end[R]+1;i<=r;i++)

				{

					if(ed[id[i]]!=time)con[id[i]]=0,ed[id[i]]=time;

					con[id[i]]++;

					if(con[id[i]]+num[L][R][id[i]]>mx or (con[id[i]]+num[L][R][id[i]]==mx and id[i]<mxid))mxid=id[i],mx=con[mxid]+num[L][R][id[i]];

				}

				ans=color[mxid];

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

			}

		}

	}

	inline void makeblock(){

		beg[1]=1;

		cn=1;

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

			if(!(i%block)){

				end[cn]=i-1;

				cn++;

				beg[cn]=i;

			}

			belong[i]=cn;

		}

		if(n%block)cn++;

		end[cn]=n;

		for (int i = 1; i <= cn; i++)

			for (int j = i; j <= cn; j++)

			{

				int makk = 0;

				for (int k = beg[i]; k <= end[j]; k++)

					num[i][j][id[k]]++;

				for (int k = 1; k <= cnt; k++){

					if(makk<num[i][j][k]) {

						makk=num[i][j][k];

						maxx[i][j]=k;

					}

				}

			}

	}

	inline void cried()

	{

		n=read(),m=read();

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

			p[i]=make_pair(read(),i);

		sort(p+1,p+n+1);

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

			if(p[i].first!=p[i-1].first or i==1)cnt++;

			color[cnt]=p[i].first;

			id[p[i].second]=cnt;

		}

		makeblock();

		solve();

	}

}

int main()

{

	star::cried();

	return 0;

}

巴特西

P4168-蒲公英-分块

最新文章

热门文章