代码求调

#include<bits/stdc++.h>
using namespace std;
int n,m;
int q,e;
struct nbfk
{
	int wfirst,wsecond,wthird;
}a[40010];
int c[1010];//区块
int l[40010],r[40010];//区块值
vector < int > d[40010];//同一数出现的下标
int cnt[1010][1010];
int tong[40010];
map < int , int > aa;
bool cmp1(nbfk x,nbfk y)
{
	return x.wfirst<y.wfirst;
}
bool cmp2(nbfk x,nbfk y)
{
	return x.wsecond<y.wsecond;
}
int ef(int ll,int rr)
{
	int w=c[ll],t=c[rr];
	int lll=ll,rrr=rr;
	while(ll<rr)
	{
		int mid=(ll+rr)/2;
		if(d[cnt[w][t]][mid]>rr)
		{
			rr=mid-1;
		}
		else
		{
			ll=mid;
		}
	}
	while(lll<rrr)
	{
		int mid=(lll+rrr)/2;
		if(d[cnt[w][t]][mid]<lll)
		{
			lll=mid+1;
		}
		else
		{
			rrr=mid;
		}
	}
	return rr-lll+1;
}
int eff(int ll,int rr,int k)
{
	int lll=ll,rrr=rr;
	while(ll<rr)
	{
		int mid=(ll+rr)>>1;
		if(d[a[k].wthird][mid]>rr)
		{
			rr=mid-1;
		}
		else
		{
			ll=mid;
		}
	}
	while(lll<rrr)
	{
		int mid=(lll+rrr)>>1;
		if(d[a[k].wthird][mid]<lll)
		{
			lll=mid+1;
		}
		else
		{
			rrr=mid;
		}
	}
	return rr-lll+1;
}
int main()
{
	cin>>n>>m;
	int t=sqrt(n);
	int len=(n+t-1)/t;//分成len个块
	for(int i=1;i<=n;++i)
	{
		cin>>a[i].wfirst;//原始值
		a[i].wsecond=i;//标记
	}
	sort(a,a+n,cmp1);
	int wcolor=1;
	a[1].wthird=wcolor;//颜色离散化
	for(int i=2;i<=n;++i)
	{
		if(a[i].wfirst!=a[i-1].wfirst)
		{
			wcolor++;//颜色离散化
		}
		a[i].wthird=wcolor;
		aa[wcolor]=a[i].wfirst;
	}//map aa[wcolor]保存每个颜色对应的实际值
	sort(a,a+n,cmp2);//复原
	int qujian=1;
	for(int i=1;i<=len*t;)
	{
		for(int j=i;j<=i+t;++j)
		{
			c[j]=qujian;
		}
		i+=t;
		qujian++;//统计区间
	}
	for(int i=1;i<=n;++i)
		d[a[i].wthird].push_back(i);//植入离散化后颜色的下标
	for(int i=1;i<=qujian;++i)
	{
		int y=i;//当前枚举到的区间
		int maxn=0;
		for(int j=l[i];j<=n;++j)
		{
			tong[a[j].wthird]++;//记录离散化颜色
			if(tong[a[j].wthird]==maxn)//颜色最优
				if(a[j].wthird<cnt[i][y])
					cnt[i][y]=a[j].wthird;
			if(tong[a[j].wthird]>maxn)//更新
			{
				maxn=tong[a[j].wthird];
				cnt[i][y]=a[j].wthird;
			}
			if(j==r[i])
				y++;//下一个区间
		}
		memset(tong,0,sizeof(tong));//重置数组
	}
	for(int i=0;i<m;++i)
	{
		cin>>q>>e;//左右下标
		int w=c[q],t=c[q];//当前下标的两个区间
		if(w==t||t-w==1)//在同一区块内或两个相邻的区块
		{
			int maxn=0,kinds=0;
			for(int i=q;i<=e;++i)//朴素
			{
				tong[a[i].wthird]++;
				if(tong[a[i].wthird]==maxn)
				{
					if(kinds>a[i].wthird)
					{
						kinds=a[i].wthird;
					}
				}
				if(tong[a[i].wthird]>maxn)
				{
					maxn=tong[a[i].wthird];
					kinds=a[i].wthird;
				}
			}
			cout<<aa[kinds]<<endl;
		}
		else//不在同一区块
		{
			int maxn=0,kinds=0;//分别是出现最大次数和种类
			tong[cnt[w][t]]=ef(q,e);//区间先判断
			maxn=tong[cnt[w][t]];//记录次数
			kinds=cnt[w][t];//记录种类
			for(int k=q;k<=r[q];++k)//扫左边
			{
				if(!tong[a[k].wthird])//若没查询过则二分查找
					tong[a[k].wthird]=eff(q,e,k);
				if(tong[a[k].wthird]==maxn)//找编号最小
				{
					if(kinds>a[k].wthird)
						kinds=a[k].wthird;
				}
				if(tong[a[k].wthird]>maxn)//更新变量
				{
					maxn=tong[a[k].wthird];
					kinds=a[k].wthird;
				}
			}
			for(int k=l[e];k<=e;++k)//扫右边
			{
				if(!tong[a[k].wthird])//若没查询过则二分查找
					tong[a[k].wthird]=eff(q,e,k);
				if(tong[a[k].wthird]==maxn)
				{
					if(kinds>a[k].wthird)
						kinds=a[k].wthird;
				}
				if(tong[a[k].wthird]>maxn)
				{
					maxn=tong[a[k].wthird];
					kinds=a[k].wthird;
				}
			}
			cout<<aa[kinds]<<endl;
		}
		memset(tong,0,sizeof(tong));//重置数组
	}
	return 0;
}