已加 快读 和 前缀和统计区间 不知道怎么优化了

已知查询的st[bel[r]] 写成 st[r]可以通过#19 原因未知

#include<bits/stdc++.h>
using namespace std;
#define maxn 40005
#define sqrtn 205
inline void read(int& n){
	n = 0;
	char ch = getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){n = (n<<3) + (n<<1) + ch - 48;ch=getchar();}
}
namespace radix{
	int re[maxn];
	int tmp[maxn];
	void radix(int* A,int n){
		for(int i = 1;i<=n;++i)tmp[i] = A[i];
			sort(tmp+1,tmp+1+n);
		for(int i = 1;i<=n;++i){
			int pos = lower_bound(tmp,tmp+n,A[i])-tmp;
			re[pos] = A[i],A[i]=pos;
		}
	}
}
int x,n;
int A[maxn];
namespace block{
	const int len = 200;
	int st[sqrtn],ed[sqrtn];
	int bel[maxn];
	int blockSum[sqrtn][maxn];
	int pre_blockSum[sqrtn][maxn];

	void init(){
		for(int i = 1;i<=n;++i){
			bel[i] = (i-1)/len;
			blockSum[bel[i]][A[i]]++;
		}
		for(int i = 1;i<=(n-1)/len;++i){
			st[i] = (i-1)*n+1;
			ed[i-1] = (i-1)*n;
		}
		ed[bel[n]] = n;
		for(int i = 1;i<=bel[n];++i){
			for(int j = 0;j<maxn;++j)pre_blockSum[i][j] = pre_blockSum[i-1][j] + blockSum[i][j];
		}
	}

	int query(int l,int r){
		int maxval=0,maxcolor = 998244353;
		if(bel[l] == bel[r]){
			vector<int> sum(maxn,0);
			for(int i = l;i<=r;++i){
				sum[A[i]]++;
				if(sum[A[i]] > maxval or (sum[A[i]] == maxval and A[i] < maxcolor)){
					maxval = sum[A[i]];
					maxcolor = A[i];
				}
			}
		}
		else{
			vector<int> sum(maxn,0);
			for(int i = l;i<=ed[bel[l]];++i){
				sum[A[i]]++;
				if(sum[A[i]] > maxval or (sum[A[i]] == maxval and A[i] < maxcolor)){
					maxval = sum[A[i]];
					maxcolor = A[i];
				}
			}
			for(int j = 0;j<maxn;++j){
				sum[j] += pre_blockSum[r][j] - pre_blockSum[l-1][j];
			}
			for(int i = 0;i<maxn;++i){
				if(maxval < sum[i])maxval=sum[i],maxcolor=i;
			}
			for(int i = st[bel[r]];i<=r;++i){
				sum[A[i]]++;
				if(sum[A[i]] > maxval or (sum[A[i]] == maxval and A[i] < maxcolor)){
					maxval = sum[A[i]];
					maxcolor = A[i];
				}
			}
		}
		return radix::re[maxcolor];
	}
}
void query(int l,int r){
	l = (l+x-1)%n+1;
	r = (r+x-1)%n+1;
	if(l>r)l^=r^=l^=r;
	x = block::query(l,r);
}
int main(){
	int q;
	read(n),read(q);
	for(int i = 1;i<=n;++i){
		read(A[i]);
	}
	radix::radix(A,n);
	while(q--){
		int l,r;
		read(l),read(r);
		query(l,r);
		printf("%d\n",x);
	}
	return 0;
}