数列分块入门 9 / 蒲公英

区间众数

这题是强制在线的，所以只有分块了，不然的话还可以莫队。。

预处理出每块之间的众数以及每个数出现的位置，查询的时候块内直接查询，不足整块的直接二分l和r，相减就是一个数出现的次数了，然后更新答案即可。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
    int X = 0, w = 0; char ch = 0;
    while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
    A ans = 1;
    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
    return ans;
}

const int N = 100005;
int n, t, id, lt[N], rt[N], a[N], f[3005][3005], freq[N], val[N], pos[N], c, _;
map<int, int> m;
vector<int> v[N];

void pretreatment(int k){
    full(freq, 0);
    int ans = 0, mx = 0;
    for(int i = lt[k]; i <= n; i ++){
        freq[a[i]] ++;
        if(freq[a[i]] > mx || (freq[a[i]] == mx && val[a[i]] < val[ans]))
            mx = freq[a[i]], ans = a[i];
        f[k][pos[i]] = ans;
    }
}

int calc(int x, int l, int r){
    int a = (int)(upper_bound(v[x].begin(), v[x].end(), r) - v[x].begin());
    int b = (int)(lower_bound(v[x].begin(), v[x].end(), l) - v[x].begin());
    return a - b;
}

int query(int l, int r){
    int p = pos[l], q = pos[r], ans = 0, mx = 0;
    if(p == q){
        for(int i = l; i <= r; i ++){
            int k = calc(a[i], l, r);
            if(k > mx || (k == mx && val[a[i]] < val[ans]))
                mx = k, ans = a[i];
        }
    }
    else{
        ans = f[p + 1][q - 1], mx = calc(ans, l, r);
        for(int i = l; i <= rt[p]; i ++){
            int k = calc(a[i], l, r);
            if(k > mx || (k == mx && val[a[i]] < val[ans]))
                mx = k, ans = a[i];
        }
        for(int i = lt[q]; i <= r; i ++){
            int k = calc(a[i], l, r);
            if(k > mx || (k == mx && val[a[i]] < val[ans]))
                mx = k, ans = a[i];
        }
    }
    return ans;
}

int main(){

    //freopen("data.txt", "r", stdin);
    n = read(), _ = read();
    for(int i = 1; i <= n; i ++){
        a[i] = read();
        if(!m[a[i]])
            m[a[i]] = ++id, val[id] = a[i];
        a[i] = m[a[i]];
        v[a[i]].push_back(i);
    }
    t = (int)sqrt(_ * ((int)(log2(0.1*n)) + 1));
    c = n / t;
    for(int i = 1; i <= t; i ++){
        lt[i] = (i - 1) * c + 1;
        rt[i] = i * c;
    }
    if(rt[t] < n) t ++, lt[t] = rt[t - 1] + 1, rt[t] = n;
    for(int i = 1; i <= t; i ++){
        for(int j = lt[i]; j <= rt[i]; j ++){
            pos[j] = i;
        }
    }
    for(int i = 1; i <= t; i ++)
        pretreatment(i);
    int x = 0;
    for(int i = 1; i <= _; i ++){
        int l = read(), r = read();
        l = (l + x - 1) % n + 1, r = (r + x - 1) % n + 1;
        if(l > r) swap(l, r);
        printf("%d
", val[query(l, r)]);
        x = val[query(l, r)];
    }
    return 0;
}