luogu4168 [Violet]蒲公英

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cmath>

#include <map>

using namespace std;

int n, m, bel[40005], a[40005], blc, f[1005][1005], cnt[40005], idx, ans;

int val[40005], uu, vv;

map<int,int> mp;

vector<int> vec[40005];

int mycnt(int uu, int vv, int ww){

    return upper_bound(vec[ww].begin(), vec[ww].end(), vv)-lower_bound(vec[ww].begin(), vec[ww].end(), uu);

}

int query(int uu, int vv){

    int tmpmax=f[bel[uu]+1][bel[vv]-1], tmpcnt=mycnt(uu, vv, tmpmax);

    if(bel[uu]==bel[vv]){

        for(int i=uu; i<=vv; i++){

            int t=mycnt(uu, vv, a[i]);

            if(t>tmpcnt || (t==tmpcnt && a[i]<tmpmax)){

                tmpmax = a[i];

                tmpcnt = t;

            }

        }

    }

    else{

        for(int i=uu; i<=bel[uu]*blc; i++){

            int t=mycnt(uu, vv, a[i]);

            if(t>tmpcnt || (t==tmpcnt && a[i]<tmpmax)){

                tmpmax = a[i];

                tmpcnt = t;

            }

        }

        for(int i=(bel[vv]-1)*blc+1; i<=vv; i++){

            int t=mycnt(uu, vv, a[i]);

            if(t>tmpcnt || (t==tmpcnt && a[i]<tmpmax)){

                tmpmax = a[i];

                tmpcnt = t;

            }

        }

    }

    return tmpmax;

}

int main(){

    cin>>n>>m;

    blc = sqrt(n*log(2)/log(n));

    for(int i=1; i<=n; i++){

        scanf("%d", &a[i]);

        val[++idx] = a[i];

        bel[i] = (i - 1) / blc + 1;

    }

    sort(val+1, val+1+n);

    idx = unique(val+1, val+1+idx) - val - 1;

    for(int i=1; i<=n; i++){

        a[i] = lower_bound(val+1, val+1+idx, a[i]) - val;

        vec[a[i]].push_back(i);

    }

    for(int i=1; i<=n; i=bel[i]*blc+1){

        memset(cnt, 0, sizeof(cnt));

        int tmpmax=0, tmpcnt=0;

        for(int j=i; j<=n; j++){

            cnt[a[j]]++;

            if(cnt[a[j]]>tmpcnt || (cnt[a[j]]==tmpcnt && a[j]<tmpmax)){

                tmpmax = a[j];

                tmpcnt = cnt[a[j]];

            }

            f[bel[i]][bel[j]] = tmpmax;

        }

    }

    while(m--){

        scanf("%d %d", &uu, &vv);

        uu = (uu + ans - 1) % n + 1;

        vv = (vv + ans - 1) % n + 1;

        if(uu>vv)	swap(uu, vv);

        ans = val[query(uu, vv)];

        printf("%d\n", ans);

    }

    return 0;

}
巴特西

luogu4168 [Violet]蒲公英

最新文章

热门文章
