蒟蒻麻了

本地AC提交WA

#include<bits/stdc++.h>
#define ll long long
#define SIZE 40005
using namespace std;
int n, m;
int a[SIZE];
int a_[SIZE];
int c[SIZE], top_c;
int c_[SIZE], top_c_;
int l[5005], r[5005], tong[SIZE];
int t;
int pos[SIZE];
vector<int>times[SIZE];
int maxnum[5005][5005], maxtimes[5005][5005]; 
void uniq(){
    for(int i = 1; i <= n; i++){
        if(c[i] == c[i + 1])continue;
        else c_[++top_c_] = c[i];
    }
}
void pre(){
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        c[++top_c] = a[i];
    }
    sort(c + 1, c + n + 1);
    uniq();
    for(int i = 1; i <= n; i++){
        int x = lower_bound(c_ + 1, c_ + top_c_ + 1, a[i]) - c_;
        a_[i] = x;
        times[x].push_back(i);
    }

    int T = sqrt(top_c_*log2(top_c_)); t = n / T;
    for(int i = 1; i <= t; i++){
        l[i] = (i - 1) * T + 1;
        r[i] = i * T;
    }
    if(r[t] < n)l[++t] = r[t - 1] + 1, r[t] = n; 
    for(int i = 1; i <= t; i++)
        for(int j = l[i]; j <= r[i]; j++)
            pos[j] = i;
}
int find1(int x, int y){
    int l = 0, r = times[y].size() - 1, mid = 0, res = 0;
    while(l <= r){
        mid = (l + r) >> 1;
        if(times[y][mid] <= x)res = mid, l = mid + 1;
        else r = mid - 1;
    }
    return res;
}
int find2(int x, int y){
    int l = 0, r = times[y].size() - 1, mid = 0, res = 0;
    while(l <= r){
        mid = (l + r) >> 1;
        if(times[y][mid] >= x)res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}
void pre_make(){
    int maxx1 = 0, maxx2 = 0, maxx3 = 0;
    for(int i = 1; i <= t; i++){
        maxx1 = maxx2 = maxx3 = 0;
        for(int j = i; j <= t; j++){
            for(int k = l[j]; k <= r[j]; k++){
                tong[a_[k]]++;
                if(tong[a_[k]] > maxx1){
                    maxx1 = tong[a_[k]], maxx2 = a[k], maxx3 = a_[k];
                }else if(tong[a_[k]] == maxx1){
                    if(a[k] < maxx2) maxx2 = a[k], maxx3 = a_[k];
                }
            }
            maxnum[i][j] = maxx2; maxtimes[i][j] = tong[maxx3];
        }
        memset(tong, 0, sizeof(tong));
    }
}
int main(){
//  freopen("4168.in","r",stdin);
//  freopen("4168.out","w",stdout);
    scanf("%d%d",&n, &m);
    pre();
    pre_make();
    int last = 0, anss = 0;
    while(m--){
        int L = 0, R = 0;
        scanf("%d%d",&L, &R);
        L = (L + anss - 1) % n + 1, R = (R + anss - 1) % n + 1;
        last = 0, anss = 0;
        if(L > R) swap(L, R);

        if(pos[R] - pos[L] <= 1){
            for(int i = L; i <= R; i++){
                int x = a_[i];
                int p1 = find2(L, x); int p2 = find1(R, x);
                if(p2 - p1 + 1 > last){
                    last = p2 - p1 + 1;anss = a[i];
                }else if(p2 - p1 + 1 == last){
                    if(a[i] < anss) anss = a[i];
                }
            }
        } else {
            for(int i = L; i <= r[pos[L]]; i++){
                int x = a_[i];
                int p1 = find2(L, x); int p2 = find1(R, x);
                if(p2 - p1 + 1 > last){
                    last = p2 - p1 + 1;anss = a[i];
                }else if(p2 - p1 + 1 == last){
                    if(a[i] < anss) anss = a[i];
                }
            }
            for(int i = l[pos[R]]; i <= R; i++){
                int x = a_[i];
                int p1 = find2(L, x); int p2 = find1(R, x);
                if(p2 - p1 + 1 > last){
                    last = p2 - p1 + 1;anss = a[i];
                }else if(p2 - p1 + 1 == last){
                    if(a[i] < anss) anss = a[i];
                }
            }
            if(maxtimes[pos[L] + 1][pos[R] - 1] > last){
                last = maxtimes[pos[L] + 1][pos[R] - 1];
                anss = maxnum[pos[L] + 1][pos[R] - 1];
            } else if(maxtimes[pos[L] + 1][pos[R] - 1] == last){
                if(anss > maxnum[pos[L] + 1][pos[R] - 1]) anss = maxnum[pos[L] + 1][pos[R] - 1];
            }
        }
        printf("%d\n",anss);
    }
    return 0;
}