RT

题目链接

蒟蒻T掉6个点，求助。

#include<bits/stdc++.h>
using namespace std;
struct PX{
	int l;
	int r;
	int wz;
}px[2000005];
int n,m;
int a[2000005][2];
int sum=0;
int aa[2000005];
int ans[2000005];
int jl[2000005];
int fk[2000005];
int gs,sq;
int tot=0;
int cnt[2000005];
int l=0,r=0;
int cmp(PX a,PX b){
	return (fk[a.l]^fk[b.l])? fk[a.l]<fk[b.l]:((fk[a.l]&1)? a.r<b.r:a.r>b.r);
}
//int cmp(query a, query b) {
//	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
//}
char buffer[1<<24],*S=buffer,puffer[1<<20],*T=puffer;
inline int read(){
	int x=0,f=1;
	while(!isdigit(*S))*S++=='-'?f=-1:1;
	while(isdigit(*S))x=x*10+*S++-'0';
	return x*f;
} 
inline void write(int x){
	if(x<0)*T++='-',x=-x;
	if(x==0)*T++='0';
	int num[15],sp=0;
	while(x){
		num[++sp]=x%10;
		x/=10;
	}
	while(sp){
		*T++=num[sp--]+'0';
	}
}
void kp(int l,int r){
	int i=l,j=r;
	int mid=a[(l+r)/2][0];
	while(i<=j){
		while(a[i][0]<mid)i++;
		while(a[j][0]>mid)j--;
		if(i<=j){
			swap(a[i][0],a[j][0]);
			swap(a[i][1],a[j][1]);
			i++;j--;
		}
	}
	if(l<j)kp(l,j);
	if(i<r)kp(i,r);
}
int main(){
//	freopen("text.in","r",stdin);
//	freopen("text.out","w",stdout);
	fread(buffer,1,1<<24,stdin);
//	scanf("%d%d",&n,&m);
	n=read(),m=read();
	sq=sqrt(n);
	gs=ceil((double)n/sq);
	for(int i=1;i<=gs;i++)
	for(int j=i*(gs-1)+1;j<=i*gs;j++)
	fk[j]=i;
	for(int i=1;i<=n;i++){
//	scanf("%d",&a[i][0]);
		a[i][0]=read();
		a[i][1]=i;
	}

	for(int i=1;i<=m;i++){
//		scanf("%d%d",&px[i].l,&px[i].r);
		px[i].l=read(),px[i].r=read();
		px[i].wz=i;
	}
	sort(px+1,px+m+1,cmp);
	kp(1,n);
	for(int i=1;i<=n;i++){
		if(a[i][0]!=a[i-1][0])sum++;
		aa[a[i][1]]=sum;
	}
	cnt[0]=200000;
	for(int i=1;i<=m;i++){
	//	printf("JVH U\n");
		while(r<px[i].r){r++;cnt[jl[aa[r]]]--;jl[aa[r]]++;cnt[jl[aa[r]]]++;tot=jl[aa[r]]>tot?jl[aa[r]]:tot;}
		while(l>px[i].l){l--;cnt[jl[aa[l]]]--;jl[aa[l]]++;cnt[jl[aa[l]]]++;tot=jl[aa[l]]>tot?jl[aa[l]]:tot;}
		while(l<px[i].l){cnt[jl[aa[l]]]--;jl[aa[l]]--;cnt[jl[aa[l]]]++;l++;tot=cnt[tot]? tot:tot-1;}
		while(r>px[i].r){cnt[jl[aa[r]]]--;jl[aa[r]]--;cnt[jl[aa[r]]]++;r--;tot=cnt[tot]? tot:tot-1;}
		ans[px[i].wz]=-tot;
	}
	for(int i=1;i<=m;i++){
		write(ans[i]);
		*T++='\n';
	}
	fwrite(puffer,1,T-puffer,stdout);
}