RE求助!!!

P4168 [Violet] 蒲公英

Mintind @ 2019-08-15 09:03:14

RE了十六个点,下下数据来看好像输入有问题,可是看了半天啥也没看出来!!!

大佬们帮帮我QAQ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

const int N = 40005, T = 1005;
int a[N], b[N], pos[N], f[T][T], v1[N];
//b用来离散化,a[i]原序列中i位置的数在b中下标 
//f[i][j]为第i块到第j块的众数,L[i]是第i块左端点下标 
int n, m, t, block, num;
std::vector<int> v[N];

int max(int a, int b)
{
    return a > b ? a : b;
} 

int count(int l, int r, int x)
{
    if(!x) return 0;
    l = std::lower_bound(v[x].begin(), v[x].end(), l) - v[x].begin();
    r = std::upper_bound(v[x].begin(), v[x].end(), r) - v[x].begin();
    //r是第一个 >= r 的数 ,符合条件的范围是[l, r) 
    return r - l;
}

void init()
{
    for(int i = 1; i <= pos[n]; ++i)
    {
        memset(v1, 0, sizeof(v1));
        int ans = 0;
        for(int j = (i - 1) * block + 1; j <= n; ++j)
        {
            v1[a[j]]++;
            if(v1[a[j]] > ans || (v1[a[j]] == ans && b[a[j]] < f[i][pos[j]]))
            {
                ans = v1[a[j]];
                f[i][pos[j]] = b[a[j]];
            }
        }
    }
}

int query(int l, int r)
{
    int p = pos[l], q = pos[r];
    int mx = f[p + 1][q - 1], ans = count(l, r, a[mx]);
    //ans不能直接等于a[mx]在p+1块到q-1块出现的次数 
    //printf("l %d r %d\n", l, r); 
    if(p == q)
    {
        for(int i = l; i <= r; ++i)
        {
            int x = count(l, r, a[i]);
            if(x > ans || (x == ans && b[a[i]] < mx))
            {
                ans = x;
                mx = b[a[i]];
            }
        }
    }
    else
    {
        for(int i = l; i <= p * block; i++)
        {
            int x = count(l, r, a[i]);
            if(x > ans || (x == ans && b[a[i]] < mx))
            {
                ans = x;
                mx = b[a[i]];
            }
        }
        for(int i = (q - 1) * block + 1; i <= r; ++i)
        {
            int x = count(l, r, a[i]);
            if(x > ans || (x == ans && b[a[i]] < mx))
            {
                ans = x;
                mx = b[a[i]];
            }
        }
    }
    return mx;
}

int main(){
    //freopen("testdata.in", "r", stdin);
    scanf("%d%d", &n, &m);
    block = max(1, n / sqrt((double)m * log2(n)));
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
        pos[i] = (i - 1) / block + 1;
    }
    std::sort(b + 1, b + n + 1);
    num = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i <= n; ++i)
    {
        a[i] = std::lower_bound(b + 1, b + num + 1, a[i]) - b;
        v[a[i]].push_back(i);
    }
    init();
    int l, r, x = 0;
    while(m--)
    {
        scanf("%d%d", &l, &r);
        //printf("m %d %d %d\n", m, l, r);
        l = (l + x - 1) % n + 1;
        r = (r + x - 1) % n + 1;
        if(l > r) std::swap(l, r);
        x = query(l, r);
        printf("%d\n", x); 
    }
    return 0;
}

by sc84bbs @ 2019-08-15 09:11:36

不,RE不求


by danefishhh @ 2019-10-21 14:57:08

@flxziq 您的vector排序了吗


by danefishhh @ 2019-10-21 15:06:07

@flxziq 它本来就是有序的...当我没说...


by danefishhh @ 2019-10-21 15:09:07

@flxziq 不过如果您过了的话能否帮我看看我的问题呢..谢谢


|