萌新求调简单分块

#include<bits/stdc++.h>
using namespace std;
int n,m,B,mx,a[500005],t[500005],ct[500005],blk[500005],c[710][710];
vector<int>bul[500005];
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int Bul(int x,int y)
{
	y=max(y,0);
	if(y>=bul[x].size())return n+1;
	return bul[x][y];
}
int main()
{
	n=read();m=read();B=sqrt(n);
	for(int i=1;i<=500000;i++)bul[i].push_back(0);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		t[i]=bul[a[i]].size();
		bul[a[i]].push_back(i);
		blk[i]=(i-1)/B+1;
	}
	for(int i=1;i<=blk[n];i++)
	{
		for(int j=(i-1)*B+1;j<=n;j++)
		{
			mx=max(mx,++ct[a[j]]);
			c[i][blk[j]]=mx;
		}
		mx=0;memset(ct,0,sizeof(ct));
	}
	for(int i=1,l,r,L,R;i<=m;i++)
	{
		cin>>l>>r;l^=mx;r^=mx;
		if(blk[l]==blk[r])
		{
			mx=0;
			for(int j=l;j<=r;j++)mx=max(mx,++ct[a[j]]);
			printf("%d\n",mx);
			for(int j=l;j<=r;j++)ct[a[j]]--;
			continue;
		}
		L=blk[l]+1;R=blk[r]-1;mx=c[L][R];
		for(int i=l;blk[i]==blk[l];i++)while(Bul(a[i],t[i]+mx)<=r)mx++;//!
		for(int i=r;blk[i]==blk[r];i--)while(Bul(a[i],t[i]-mx)>=l)mx++;//!
		printf("%d\n",mx);
	}
}