分块 TLE#18 #19 求调

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

已知查询的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;
}