WA+T求调

#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 3e5 + 5;
const int sqr = 800;
int f[sqr][N];//f[i][j]表示前i个块中j出现的次数
int g[sqr][sqr];//g[i][j]表示第i到j块中最小的众数
int a[N];
int cl[N],cr[N],tag[N];
vector<int> tmp;
map<int,int> mp;
int idx;
int nums[N];
inline void init(){
    int B = sqrt(n);
    int len = (n%B == 0 ? n/B : n/B+1);
    for(int i = 1;i <= len;i ++){//get G
        memset(nums,0,sizeof(nums));
        pair<int,int> maxx = {INT_MIN,0};
        for(int j = i;j <= len;j ++){
            for(int k = (j - 1) * B + 1;k <= min(n,j*B);k ++){
                nums[a[k]] ++;
                if(nums[a[k]]>maxx.first){
                    maxx = {nums[a[k]],a[k]};
                }
                else if(nums[a[k]] == maxx.first)   maxx.second = min(maxx.second,a[k]);
            }
            g[i][j] = maxx.second;
        }
    }

    for(int i = 1;i <= len;i ++){//get F
        memset(nums,0,sizeof(nums));
        for(int j = (i - 1)*B + 1;j <= min(i*B,n);j ++){
            nums[a[i]] ++;
        }
        for(int j = (i - 1)*B + 1;j <= min(i*B,n);j ++){
            f[i][a[j]] = f[i-1][a[j]] + nums[a[j]];
        }
    }

    for(int i = 1;i <= len;i ++){
        for(int j = (i - 1)*B + 1;j <= min(i*B,n);j ++){
            cl[j] = (i - 1)*B + 1;
            cr[j] = min(i*B,n);
            tag[j] = i;
        }
    }
}
inline int query(int l,int r){
    if(tag[r]-tag[l]+1 <= 2){
        memset(nums,0,sizeof(nums));
        pair<int,int> maxx = {INT_MIN,0};
        for(int i = l;i <= r;i ++){
            nums[a[i]] ++ ;
            if(nums[a[i]] > maxx.first)   maxx = {nums[a[i]],a[i]};
            else if(nums[a[i]] == maxx.first)   maxx.second = min(maxx.second,a[i]);
        }
         return tmp[maxx.second - 1];
    }
    else{
        pair<int,int> maxx = {f[tag[r] - 1][g[tag[l] + 1][tag[r] - 1]] - f[tag[l]][g[tag[l] + 1][tag[r] - 1]],g[tag[l] + 1][tag[r] - 1]};
        memset(nums,0,sizeof(nums));
        // nums[g[tag[l] + 1][tag[r] - 1]] = f[r - 1][g[tag[l] + 1][tag[r] - 1]] - f[l][g[tag[l] + 1][tag[r] - 1]];
        for(int i = l;i <= cr[l];i ++){
            nums[a[i]] ++ ;
            if(nums[a[i]] + f[tag[r] - 1][a[i]]-f[tag[l]][a[i]] > maxx.first)   maxx = {nums[a[i]] + f[tag[r] - 1][a[i]]-f[tag[l]][a[i]],a[i]};
            else if(nums[a[i]] + f[tag[r] - 1][a[i]]-f[tag[l]][a[i]] == maxx.first)   maxx.second = min(maxx.second,a[i]);
        }
        for(int i = cl[r];i <= r;i ++){
            nums[a[i]] ++ ;
            if(nums[a[i]] + f[tag[r] - 1][a[i]]-f[tag[l]][a[i]] > maxx.first)   maxx = {nums[a[i]] + f[tag[r] - 1][a[i]]-f[tag[l]][a[i]],a[i]};
            else if(nums[a[i]] + f[tag[r] - 1][a[i]]-f[tag[l]][a[i]] == maxx.first)   maxx.second = min(maxx.second,a[i]);
        }
         return tmp[maxx.second - 1];
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        tmp.push_back(a[i]);
    }
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(auto v:tmp){
        mp[v] = ++idx;//返回的话就是tmp[a[i] - 1]
    }
    for(int i = 1;i <= n;i ++){
        a[i] = mp[a[i]];
    }
    init();
    for(int i = 1;i <= n;i ++){
        int l,r;
        cin >> l >> r;
        cout << query(l,r) << "\n";
    }
    return 0;
}