可怜萌新小妹,求助各位大佬

P4168 [Violet] 蒲公英

灼眼的夏娜 @ 2019-09-22 14:39:08

有哪位大佬帮忙看看这份代码哪里有问题

#include<bits/stdc++.h>
#define R register

using namespace std;
const int N = 40005;
int n,m,num,x,cnt,len;
int b[N],tag[N],a[N],ll[N],rr[N],ton[N];
int sum[300][N],p[300][300];

inline int query(int l,int r) {
    R int now = 0,fr = tag[l],to = tag[r];
    if(to - fr <= 1) {
        for(R int i = l;i <= r;++ i) ton[a[i]]++;
        for(R int i = l;i <= r;++ i) 
            if(ton[a[i]] + (a[i] < now) > ton[now])
                now = a[i];
        for(R int i = l;i <= r;++ i) ton[a[i]] = 0;
        return now;
    }
    for(R int i = l;i <= rr[fr];++ i) ton[a[i]] ++;
    for(R int i = ll[to];i <= r;++ i) ton[a[i]] ++;
    -- to;
    now = p[fr + 1][to];
    for(R int i = l;i <= rr[fr];++ i)
        if(sum[to][now] - sum[fr][now] + ton[now] < sum[to][a[i]] + (a[i] < now) - sum[fr][a[i]] + ton[a[i]])
            now = a[i];
    for(R int i = ll[to + 1];i <= r;++ i)
        if(sum[to][now] - sum[fr][now] + ton[now] < sum[to][a[i]] + (a[i] < now) - sum[fr][a[i]] + ton[a[i]])
            now = a[i]; 
    ++ to;
    for(R int i = l;i <= rr[fr];++ i) ton[a[i]] = 0;
    for(R int i = ll[to];i <= r;++ i) ton[a[i]] = 0;
    return now;
}

inline void init() {
    for(R int i = 1;i <= num;++ i) {
        for(R int j = ll[i];j <= rr[i];++ j) sum[i][a[j]] ++;
        for(R int j = 1;j <= cnt;++ j) sum[i][j] += sum[i - 1][j];
    }
    for(R int i = 1;i <= num;++ i)
    for(R int j = i;j <= num;++ j) {
        R int now = p[i][j - 1];
        for(R int k = ll[j];k <= rr[j];++ k) {
            if(sum[j][a[k]] - sum[i - 1][a[k]] + (a[k] < now) > sum[j][now] - sum[i - 1][now])
                now = a[k];
        }
        p[i][j] = now;
    }
}

int main() {
//  freopen("violet.in","r",stdin);
//  freopen("violet.out","w",stdout);
    scanf("%d%d",&n,&m);
    len = sqrt(n);
    for(R int i = 1;i <= n;++ i) {
        scanf("%d",&a[i]);
        tag[i] = (i - 1) / len + 1;
        b[i] = a[i];    
    }

    sort(b + 1,b + n + 1);
    cnt = unique(b + 1,b + n + 1) - b - 1;
    for(R int i = 1;i <= n;++ i) a[i] = lower_bound(b + 1,b + cnt + 1,a[i]) - b;

    if(len * len == n) num = len;
    else num = len + 1;
    for(R int i = 1;i <= num;++ i) {
        ll[i] = (i - 1) * len + 1;
        rr[i] = min(n,i * len);
    } 

    init();

    int X = 0;
    for(R int i = 1,l,r;i <= m;++ i) {
        scanf("%d%d",&l,&r);
        l = (l + X - 1) % n + 1,r = (r + X - 1) % n + 1;
        if(l > r) swap(l,r);
        x = query(l,r);
        printf("%d\n", X = b[x]);
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

by BinDir0 @ 2019-09-22 15:24:07

@灼眼的夏娜 哇一千多组


by BinDir0 @ 2019-09-22 15:24:22

窝拍了两百多组就放弃了


by 言和YanHe @ 2019-10-07 08:50:25

@恨妹不成穹 我拍几十组就放弃了/xyx/baojin(


by BinDir0 @ 2019-10-07 15:28:52

@HFOI菠萝 /xyx


上一页 |