\(\text{Problem}\)
强制在线静态询问区间众数
\(\text{Solution}\)
不得不说 \(vector\) 是真的慢
做 \(LOJ\) 数列分块入门 \(9\) 卡时间卡了两个小时没成功
说说够快得做法
对原数列分块
考虑已经预处理出任意两块之间得答案
散块中出现的颜色可以让其在整块中失败后翻盘
其它颜色就没机会了
也就是说只考虑散块中出现的颜色和整块预处理出的答案
暴力扫散块,再加上它在整块中的个数就是它的出现次数,取最大值即可
达成此点还需维护每种颜色在块中的前缀和
在考虑预处理,参考询问方法把块 \(i\) 到 \(j\) 的答案看成块 \(i\) 到 \(j-1\) 再多了第 \(j\) 块
于是完成
\(\text{Code}\)
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#define re register
using namespace std;
const int N = 1e5 + 5;
int n, m, lst, st[N], ed[N], id[N], a[N], b[N], f[401][401], buc[N], PreSum[N][401];
inline int Count(int c, int l, int r){return PreSum[c][r] - PreSum[c][l - 1];}
inline void Prework()
{
sort(b + 1, b + n + 1);
int num = sqrt(n) + 1, len = unique(b + 1, b + n + 1) - b - 1;
for(re int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
for(re int i = 1; i <= num; i++)
{
st[i] = ed[i - 1] + 1, ed[i] = (i == num ? n : ed[i - 1] + n / num);
for(re int j = 1; j <= len; j++) PreSum[j][i] = PreSum[j][i - 1];
for(re int j = st[i]; j <= ed[i]; j++) id[j] = i, ++PreSum[a[j]][i];
}
for(re int i = 1; i <= num; i++)
for(re int j = i; j <= num; j++)
{
int cl = 0, num = 0, nu;
for(re int k = st[j]; k <= ed[j]; k++)
{
nu = Count(a[k], i, j);
if (nu > num) num = nu, cl = a[k];
else if (nu == num) cl = min(cl, a[k]);
}
if (i ^ j)
{
nu = Count(f[i][j - 1], i, j);
if (nu > num) num = nu, cl = f[i][j - 1];
else if (nu == num) cl = min(cl, f[i][j - 1]);
}
f[i][j] = cl;
}
}
inline int Query(int l, int r)
{
int x = id[l], y = id[r];
if (x == y)
{
int cl = 0, num = 0, cnt = 0, nu;
for(re int k = l; k <= r; ++buc[a[k]], k++);
for(re int k = l; k <= r; k++)
{
nu = buc[a[k]], buc[a[k]] = 0;
if (nu > num) num = nu, cl = a[k];
else if (nu == num) cl = min(cl, a[k]);
}
return b[cl];
}
int cl = f[x + 1][y - 1], num = Count(cl, x + 1, y - 1), nu, cnt = 0;
for(re int k = l; k <= ed[x]; ++buc[a[k]], k++);
for(re int k = st[y]; k <= r; ++buc[a[k]], k++);
for(re int k = l; k <= ed[x]; k++)
{
nu = buc[a[k]] + Count(a[k], x + 1, y - 1), buc[a[k]] = 0;
if (nu > num) num = nu, cl = a[k];
else if (nu == num) cl = min(cl, a[k]);
}
for(re int k = st[y]; k <= r; k++)
{
nu = buc[a[k]] + Count(a[k], x + 1, y - 1), buc[a[k]] = 0;
if (nu > num) num = nu, cl = a[k];
else if (nu == num) cl = min(cl, a[k]);
}
return b[cl];
}
inline void read(int &x)
{
x = 0; char ch = getchar(); int f = 1;
for(; !isdigit(ch); f = (ch == '-' ? -1 : f), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
if (f - 1) x = ~x + 1;
}
int main()
{
read(n), read(m);
for(re int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];
Prework();
for(re int l, r; m; --m)
{
read(l), read(r), l = (l + lst - 1) % n + 1, r = (r + lst - 1) % n + 1;
if (l > r) swap(l, r);
printf("%d\n", lst = Query(l, r));
}
}