P1997 faebdc 的烦恼

莫队模板,求调或提供hack数据

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cctype>
using namespace std;
const int N=1e6+10;
inline int read(){int c=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) c=(c<<3)+(c<<1)+ch-48;return c*w;}
void print(int x){if(x>9) print(x/10);putchar(x%10+48);}
struct query
{
	int l,r;
	int id;
}q[N];
int pos[N],aa[N],cnt[N],sum[N],ans[N];//cnt记录a数组中每个数的出现次数,sum记录cnt数组中每个数的出现次数 
int n,size,t,m,now;
int cmp(query a,query b){return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);}
inline void add(int x)
{
	sum[cnt[aa[x]]]--;
	sum[++cnt[aa[x]]]++;
	if(cnt[aa[x]]>now) now=cnt[aa[x]];
}
inline void del(int x)
{
	if(sum[cnt[aa[x]]]==1&&now==cnt[aa[x]]) now=cnt[aa[x]]-1;
	sum[cnt[aa[x]]--]--;
}
int main()
{
	scanf("%d%d",&n,&m);
	t=sqrt(n);
	size=ceil((double)n/t);
	for(int i=1;i<=size;i++)
		for(int j=(i-1)*t+1;j<=i*t;j++)
			pos[j]=i;
	for(int i=1;i<=n;i++) scanf("%d",&aa[i]),aa[i]+=1e5;
	for(int i=1;i<=m;i++)
	{
		q[i].l=read(),q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		int ql=q[i].l,qr=q[i].r;
		while(l<ql) del(l++);
		while(l>ql) add(--l);
		while(r<qr) add(++r);
		while(r>qr) del(r--);
		ans[q[i].id]=now;
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}