[BZOJ2724][Violet 6]蒲公英
试题描述
输入
修正一下
l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1
输出
输入示例
输出示例
数据规模及约定
修正下：
n <= 40000, m <= 50000
题解
分块，先预处理出 f[i][j] 表示第 i 块到第 j 块的众数，枚举起点 i 然后扫一遍就好了。
其次是询问，对于一个询问 [ql, qr]，其中 ql 属于块 l，qr 属于块 r，众数要么是 f[l+1][r-1]，要么是不完整块中的数，所以我们需要搞一个 calc(l, r, x) 功能，表示询问 [l, r] 中 x 出现的次数，有了这个功能后就可以做到把答案初始设为 f[l+1][r-1]（O(1)），然后 O(sqrt(n)) 暴力枚举不完整块中的数，如果出现次数比当前的多，就更新答案。
这个 calc() 函数可以这样搞：把所有数离散，每个数的位置记下来，然后当询问 calc(l, r, x) 在 x 的位置序列上二分一下就可以计算了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std; const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 40010
#define maxq 210
int n, m, num[maxn], A[maxn], st[maxq], en[maxq], bl[maxn], cntb, f[maxq][maxq], cntn[maxn]; vector <int> pos[maxn];
int calc(int l, int r, int x) {
return upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);
}
int query(int ql, int qr) {
int l = bl[ql], r = bl[qr];
if(r - l <= 1) {
int ans = A[ql], mx = calc(ql, qr, ans);
for(int i = ql + 1; i <= qr; i++) {
int tmp = calc(ql, qr, A[i]);
if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;
}
return ans;
}
int ans = f[l+1][r-1], mx = calc(ql, qr, ans);
for(int i = ql; i <= en[l]; i++) {
int tmp = calc(ql, qr, A[i]);
if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;
}
for(int i = st[r]; i <= qr; i++) {
int tmp = calc(ql, qr, A[i]);
if(mx < tmp || (mx == tmp && ans > A[i])) ans = A[i], mx = tmp;
}
return ans;
} int main() {
n = read(); m = read();
int siz = (int)sqrt(n + .5);
for(int i = 1; i <= n; i++) {
num[i] = A[i] = read();
int p = (i - 1) / siz + 1; cntb = p;
if(!st[p]) st[p] = i;
en[p] = i;
bl[i] = p;
} sort(num + 1, num + n + 1);
for(int i = 1; i <= n; i++) A[i] = lower_bound(num + 1, num + n + 1, A[i]) - num;
for(int i = 1; i <= cntb; i++) {
memset(cntn, 0, sizeof(cntn));
for(int j = st[i]; j <= n; j++) {
cntn[A[j]]++;
int r = bl[j];
if(r > i && !f[i][r]) f[i][r] = f[i][r-1];
if(!f[i][r] || cntn[f[i][r]] < cntn[A[j]] || (cntn[f[i][r]] == cntn[A[j]] && f[i][r] > A[j]))
f[i][r] = A[j];
}
}
for(int i = 1; i <= n; i++) pos[A[i]].push_back(i); int x = 0;
while(m--) {
int l = (read() + x - 1) % n + 1, r = (read() + x - 1) % n + 1;
if(l > r) swap(l, r);
int tmp = query(l, r);
printf("%d\n", num[tmp]);
x = num[tmp];
} return 0;
}