BZOJ 2724 [Violet 6] 蒲公英

题目描述

输入

修正一下

l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1

输出

样例输入

6 3
1 2 3 2 1 2
1 5
3 6
1 5

样例输出

1
2
1

修正下：
n <= 40000, m <= 50000

题解

f(i,j)表示第 i 块到第 j 块的众数。
为每一个数开vector<> 存他的位置
在求得时候二分就可以了
详见《区间众数解题报告 - 陈立杰》

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
int n, m, block, tot;
int a[40005], Index, v[40005];
int in[40005];
int f[4000][4000], num[40005];
map<int, int> mp;
vector<int> x[40005];
void Init(int u)
{
    memset(num, 0, sizeof(num));
    int Max = 0, ans = 0;
    for (int i = (u - 1) * block + 1; i <= n; i++)
    {
        num[a[i]]++;
        if (num[a[i]] > Max || (num[a[i]] == Max && v[a[i]] < v[ans]))
            ans = a[i], Max = num[a[i]];
        f[u][in[i]] = ans;
    }
}
int Query(int l, int r, int u)
{
    return upper_bound(x[u].begin(), x[u].end(), r) - lower_bound(x[u].begin(), x[u].end(), l);
}
int Query(int l, int r)
{
    int ans, Max;
    ans = f[in[l] + 1][in[r] - 1];
    Max = Query(l, r, ans);
    for (int i = l; i <= min(in[l] * block, r); i++)
    {
        int now = Query(l, r, a[i]);
        if (now > Max || (now == Max && v[a[i]] < v[ans]))
            ans = a[i], Max = now;
    }
    if (in[l] != in[r])
    {
        for (int i = (in[r] - 1) * block + 1; i <= r; i++)
        {
            int now = Query(l, r, a[i]);
            if (now > Max || (now == Max && v[a[i]] < v[ans]))
                ans = a[i], Max = now;
        }
    }
    return ans;
}
int main()
{
    //freopen("input.in", "r", stdin);
    scanf("%d%d", &n, &m);
    block = 200;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (!mp[a[i]])
        {
            mp[a[i]] = ++Index;
            v[Index] = a[i];
        }
        a[i] = mp[a[i]];
        x[a[i]].push_back(i);
        in[i] = (i - 1) / block + 1;
    }
    tot = in[n];
    for (int i = 1; i <= tot; i++)
        Init(i);
    int l, r, ans = 0;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &l, &r);
        l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
        if (l > r)
            swap(l, r);
        ans = v[Query(l, r)];
        printf("%d\n", ans);
    }
    //while (1)
    ;
}

附数据生成器

#include<cstdio>  
#include<ctime>  
#include<cstdlib>  
#include<iostream>  
using namespace std;  
int main()  
{  
    freopen("input.in","w",stdout);  
    int n,m;  
    n=40000;m=50000;  
    srand(time(0));  
    printf("%d %d\n",n,m);  
    for (int i=1;i<=n;i++){  
        int x=rand()*rand()%1000000000+1;  
        cout<<x<<" ";  
    }  
    printf("\n");  
    for (int i=1;i<=m;i++){  
        int l=rand()*rand()%n+1;  
        int r=rand()*rand()%n+1;  
        cout<<l<<" "<<r<<endl;  
    }  
    return 0;  
}