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
额