Cgod @ 2018-06-03 14:26:27
15 13
96 25 40 2 50 25 48 9 93 43 25 75 86 21 21
95 83
93 98
71 12
40 71
26 52
30 77
73 47
10 51
19 93
21 53
40 80
56 11
52 25
#include <bits/stdc++.h>
using namespace std;
const int maxn = 40010;
int n, m, block, tot, a[maxn], cnt[maxn][210], f[210][210], tmp[maxn], c[maxn];
int belong[maxn], bl[210], br[210];
vector<int> v;
void init() {
for (int i = 1; i <= n; i++) {
cnt[a[i]][belong[i]]++;
}
for (int j = 1; j <= belong[n]; j++) {
for (int i = 1; i <= tot; i++) {
cnt[i][j] += cnt[i][j - 1];
}
}
for (int i = 1; i <= belong[n]; i++) {
memset(tmp, 0, sizeof(tmp));
for (int j = i, cur = 0; j <= belong[n]; j++) {
for (int k = bl[j]; k <= br[j]; k++) {
tmp[a[k]]++;
if (!cur || tmp[a[k]] > tmp[cur] || (tmp[a[k]] == tmp[cur] && a[k] < cur)) {
cur = a[k];
}
}
f[i][j] = cur;
}
}
}
int query(int l, int r) {
int res = 0, val = 0;
if (belong[l] == belong[r] || belong[l] + 1 == belong[r]) {
for (int i = l; i <= r; i++) {
c[a[i]] = 0;
}
for (int i = l; i <= r; i++) {
c[a[i]]++;
if (!res || c[a[i]] > c[res] || (c[a[i]] == c[res] && a[i] < res)) {
res = a[i];
}
}
} else {
tot = 0;
res = f[belong[l] + 1][belong[r] - 1], val = cnt[res][belong[r] - 1] - cnt[res][belong[l]];
for (int i = l; i <= br[belong[l]]; i++) {
tmp[++tot] = a[i];
}
for (int i = bl[belong[r]]; i <= r; i++) {
tmp[++tot] = a[i];
}
for (int i = 1; i <= tot; i++) {
c[tmp[i]] = cnt[tmp[i]][belong[r] - 1] - cnt[tmp[i]][belong[l]];
}
for (int i = 1; i <= tot; i++) {
c[tmp[i]]++;
}
for (int i = 1; i <= tot; i++) {
if (!res || c[tmp[i]] > val || (c[tmp[i]] == val && tmp[i] < res)) {
res = tmp[i];
val = c[tmp[i]];
}
}
for (int i = 1; i <= tot; i++) {
c[tmp[i]] = 0;
}
}
return res;
}
int main() {
scanf("%d %d", &n, &m);
block = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
belong[i] = (i - 1) / block + 1;
if (!bl[belong[i]]) {
bl[belong[i]] = i;
}
br[belong[i]] = i;
v.push_back(a[i]);
}
sort(v.begin(), v.end());
int end = unique(v.begin(), v.end()) - v.begin();
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(v.begin(), v.begin() + end, a[i]) - v.begin() + 1;
}
tot = n - end;
init();
int lastans = 0;
while (m--) {
int l, r;
scanf("%d %d", &l, &r);
l = (l + lastans - 1) % n + 1, r = (r + lastans - 1) % n + 1;
if (l > r) {
swap(l, r);
}
printf("%d %d\n",l,r);
printf("%d\n", lastans = v[query(l, r) - 1]);
}
return 0;
}
题解里的代码,但我手玩时发现这个运行输出的明显有问题,是我太菜了还是代码有问题???
by Cgod @ 2018-06-03 14:40:35
还有这个,这题数据怕有鬼。。。
13 4
88 40 27 28 19 78 77 53 78 7 58 72 96
17 27
85 94
39 57
93 23
by hellomath @ 2018-06-03 15:01:24
所以我菜呀!谁能帮我找出问题?
by hellomath @ 2018-06-26 22:52:10
@cx233666 谢谢,现在已更新题解。
by Erina @ 2018-11-04 21:55:34
都过了,但是就是0分