1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <vector>
5
#include <map>
6
#include <cmath>
7
using namespace std;
8
int n, m, block, tot;
9
int a[40005], Index, v[40005];
10
int in[40005];
11
int f[4000][4000], num[40005];
12
map<int, int> mp;
13
vector<int> x[40005];
14
void Init(int u)
15
{
16
    memset(num, 0, sizeof(num));
17
    int Max = 0, ans = 0;
18
    for (int i = (u - 1) * block + 1; i <= n; i++)
19
    {
20
        num[a[i]]++;
21
        if (num[a[i]] > Max || (num[a[i]] == Max && v[a[i]] < v[ans]))
22
            ans = a[i], Max = num[a[i]];
23
        f[u][in[i]] = ans;
24
    }
25
}
26
int Query(int l, int r, int u)
27
{
28
    return upper_bound(x[u].begin(), x[u].end(), r) - lower_bound(x[u].begin(), x[u].end(), l);
29
}
30
int Query(int l, int r)
31
{
32
    int ans, Max;
33
    ans = f[in[l] + 1][in[r] - 1];
34
    Max = Query(l, r, ans);
35
    for (int i = l; i <= min(in[l] * block, r); i++)
36
    {
37
        int now = Query(l, r, a[i]);
38
        if (now > Max || (now == Max && v[a[i]] < v[ans]))
39
            ans = a[i], Max = now;
40
    }
41
    if (in[l] != in[r])
42
    {
43
        for (int i = (in[r] - 1) * block + 1; i <= r; i++)
44
        {
45
            int now = Query(l, r, a[i]);
46
            if (now > Max || (now == Max && v[a[i]] < v[ans]))
47
                ans = a[i], Max = now;
48
        }
49
    }
50
    return ans;
51
}
52
int main()
53
{
54
    //freopen("input.in", "r", stdin);
55
    scanf("%d%d", &n, &m);
56
    block = 200;
57
    for (int i = 1; i <= n; i++)
58
    {
59
        scanf("%d", &a[i]);
60
        if (!mp[a[i]])
61
        {
62
            mp[a[i]] = ++Index;
63
            v[Index] = a[i];
64
        }
65
        a[i] = mp[a[i]];
66
        x[a[i]].push_back(i);
67
        in[i] = (i - 1) / block + 1;
68
    }
69
    tot = in[n];
70
    for (int i = 1; i <= tot; i++)
71
        Init(i);
72
    int l, r, ans = 0;
73
    for (int i = 1; i <= m; i++)
74
    {
75
        scanf("%d%d", &l, &r);
76
        l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
77
        if (l > r)
78
            swap(l, r);
79
        ans = v[Query(l, r)];
80
        printf("%d\n", ans);
81
    }
82
    //while (1)
83
    ;
84
}

1
#include<cstdio>
2
#include<ctime>
3
#include<cstdlib>
4
#include<iostream>
5
using namespace std;
6
int main()
7
{
8
    freopen("input.in","w",stdout);
9
    int n,m;
10
    n=40000;m=50000;
11
    srand(time(0));
12
    printf("%d %d\n",n,m);
13
    for (int i=1;i<=n;i++){
14
        int x=rand()*rand()%1000000000+1;
15
        cout<<x<<" ";
16
    }
17
    printf("\n");
18
    for (int i=1;i<=m;i++){
19
        int l=rand()*rand()%n+1;
20
        int r=rand()*rand()%n+1;
21
        cout<<l<<" "<<r<<endl;
22
    }
23
    return 0;
24
}