救救刚学A+Bproblem的妹子

P4168 [Violet] 蒲公英

Silent_E @ 2019-05-21 21:10:59

有什么错啊

//#include<bits/stdc++.h>

#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug() puts("FBI WARNING!")
#define ll long long

using namespace std;
const int N = 2000 + 5;
const int MAX = 40000 + 5;

int n, m, last;
int limit, bs[MAX], a[MAX], b[MAX], t[MAX], sum[N][MAX], L[MAX], R[MAX], c[N][N], cover[MAX];

inline int read(){
    int f = 1, x = 0;char ch;
    do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0'||ch>'9');
    do {x = x*10+ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9'); 
    return f*x;
}

inline void pre() {
    for (int i = 1;i <= n; ++i) a[i] = b[i] = read();
    /*离散*/
    sort(b + 1, b + n + 1);
    int op = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1;i <= n; ++i) {
        a[i] = lower_bound(b + 1, b + op + 1, a[i]) - b;
    }
    /*分块*/
    limit = sqrt(n);
    for (int i = 1;i <= n; ++i) {
        bs[i] = i / limit + 1;
        sum[bs[i]][a[i]]++;
        if(L[i / limit] == 0){
            L[i / limit] = i;
        }
        R[i / limit] = i;
    }
    /*
    预处理 
    */
    for (int i = 1;i <= bs[n]; ++i) {
        for (int j = 1;j <= op; ++j) {
            sum[i][j] += sum[i-1][j];
        }
    }
    for (int i = 1;i <= bs[n]; ++i) {
        int be = L[i], nows = 0;
        for (int j = be;j <= n; ++j) {
            if ((++cover[a[j]] > cover[nows]) || (cover[a[j]] == cover[nows] && a[j] < nows)) nows = a[j];
            c[i][bs[j]] = nows;
        }
        for (int j = be;j <= n; ++j) --cover[a[j]];
    }
}

inline int find(int l, int r) {
    if (bs[r] - bs[l] <= 4) {
        int ans = 0;
        for (int i = l;i <= r; ++i) {
            if (++cover[a[i]] > cover[ans] || (cover[a[i]] == cover[ans] && ans > a[i])) ans = a[i];
        }
        for (int i = l;i <= r; ++i) --cover[a[i]];
        return b[ans];
    }   

    int x = bs[l] + 1, y = bs[r] - 1;
    int LL = L[x], RR = R[y];
    int ans = c[x][y];
    for (int i = l;i < LL; ++i) {
        ++cover[a[i]];
        if (cover[a[i]] + sum[y][a[i]] - sum[x-1][a[i]] > cover[ans] + sum[y][ans] - sum[x-1][ans]) {
            ans = a[i];
        }
        else if (cover[a[i]] + sum[y][a[i]] - sum[x-1][a[i]] == cover[ans] + sum[y][ans] - sum[x-1][ans] && a[i] < ans) {
            ans = a[i];
        }
    } 
    for (int i = RR + 1;i <= r; ++i) {
        ++cover[a[i]];
        if (cover[a[i]] + sum[y][a[i]] - sum[x-1][a[i]] > cover[ans] + sum[y][ans] - sum[x-1][ans]) {
            ans = a[i];
        }
        else if (cover[a[i]] + sum[y][a[i]] - sum[x-1][a[i]] == cover[ans] + sum[y][ans] - sum[x-1][ans] && a[i] < ans) {
            ans = a[i];
        }       
    }
    for (int i = l;i < LL; ++i) --cover[a[i]];
    for (int i = RR + 1;i <= r; ++i) --cover[a[i]];
    return b[ans];
}
inline void open() {
    freopen("i","r",stdin);
    freopen("o0","w",stdout);   
} 
int main(){
//  open();
    n = read(), m = read();
    pre();
    for (int i = 1;i <= m; ++i) {
        int l = read(), r = read();
        l = (l + last - 1) % n + 1, r = (r + last - 1) % n + 1;
        if (l > r) swap(l, r);
        last = find(l, r);
        printf("%d\n", last);
    }
    return 0;
}

by 辰星凌 @ 2019-05-21 21:11:26

妹子好


by 辰星凌 @ 2019-05-21 21:11:39

不知道哪有错啊


by PandZz @ 2019-05-21 21:13:13

小姐姐好


by Hzao @ 2019-05-21 21:13:25

楼上的关注点好奇怪啊。


by PandZz @ 2019-05-21 21:13:32

没看到有什么错啊


by Atmizz @ 2019-05-21 21:13:52

为什么要强调你是个妹子?!


by IC_QQQ @ 2019-05-21 21:13:57

Orz

作证,真是可爱的女装妹子


by DocMander‮ @ 2019-05-21 21:14:48

我证明,lz是女装大佬


by 我不认识你 @ 2019-05-21 21:15:13

小姐姐好

不知道哪错了


by ⚡皮卡丘⚡ @ 2019-05-21 21:15:15


| 下一页