Zack_zhu @ 2021-06-26 13:37:26
[题目链接](https://www.luogu.com.cn/problem/P4168)
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 4e4+5;
const int MAXQ = 505;
int k[MAXQ][MAXQ],s[MAXQ][MAXN],a[MAXN],lsh[MAXN],l[MAXQ],r[MAXQ],t[MAXN],p[MAXN],pos[MAXN],maxx,now,cnt,n,m,x,y,ans,block;
template <typename T>
inline void read(T &s)
{
s = 0;
bool w = false;
char ch = getchar();
while(ch < '0'||ch > '9')
{
if(ch == '-')
w = true;
ch = getchar();
}
while(ch >= '0'&&ch <= '9')
{
s = (s<<3)+(s<<1)+(ch^48);
ch = getchar();
}
s = w == true ? -s:s;
return;
}
inline void in_block()
{
memset(t,0,sizeof(t));
maxx = 0;
for(int i = x;i <= y;i++)//暴力扫
{
t[a[i]]++;
if(t[maxx] < t[a[i]])
maxx = a[i];
if(t[maxx] == t[a[i]])
maxx = min(maxx,a[i]);
}
ans = p[maxx];
return;
}
inline void out_block()
{
memset(t,0,sizeof(t));
maxx = 0;
for(int i = x;i <= r[pos[x]];i++)//暴力查整块左边的
{
t[a[i]]++;
if(t[maxx] < t[a[i]])
maxx = a[i];
if(t[maxx] == t[a[i]])
maxx = min(maxx,a[i]);
}
for(int i = l[pos[y]];i <= y;i++)//暴力查整块右边的
{
t[a[i]]++;
if(t[maxx] < t[a[i]])
maxx = a[i];
if(t[maxx] == t[a[i]])
maxx = min(maxx,a[i]);
}
if(maxx == k[pos[x] + 1][pos[y] - 1])//如果相等，直接还原并返回（BTW：p为离散化前对应的值）
ans = p[maxx];
else
{
t[maxx] += s[pos[y] - 1][maxx] - s[pos[x]][maxx];//加上块内的边上求得的众数
int ans2 = t[k[pos[x] + 1][pos[y] - 1]] + s[pos[y] - 1][k[pos[x] + 1][pos[y] - 1]] - s[pos[x]][k[pos[x] + 1][pos[y] - 1]];//块内众数的个数
if(t[maxx] > ans2)//选择答案
ans = p[maxx];
else if(t[maxx] == ans2)
ans = p[min(maxx,k[pos[x] + 1][pos[y] - 1])];
else
ans = p[k[pos[x] + 1][pos[y] - 1]];
}
return;
}
int main()
{
read(n);
read(m);
block = sqrt(n);
for(int i = 1;i <= n;i++)
{
read(a[i]);
lsh[i] = a[i];
}
sort(lsh+1,lsh+1+n);//离散化
cnt = unique(lsh+1,lsh+1+n) - lsh - 1;
for(int i = 1;i <= n;i++)
now = a[i],a[i] = lower_bound(lsh+1,lsh+1+cnt,a[i]) - lsh,p[a[i]] = now;
for(int i = 1;i <= block;i++)//预处理左右端点
{
l[i] = (i - 1) * block + 1;
r[i] = i * block;
}
if(r[block] < n)
{
l[++block] = r[block - 1] + 1;
r[block] = n;
}
for(int i = 1;i <= block;i++)
for(int j = l[i];j <= r[i];j++)
pos[j] = i;//每一个位置对应的块的编号
for(int i = 1;i <= block;i++)
{
for(int j = 1;j <= cnt;j++)
s[i][j] += s[i-1][j];//sum数组处理 1 ~ i中j的个数
for(int j = l[i];j <= r[i];j++)
s[i][a[j]]++;
}
for(int i = 1;i <= block;i++)
{
memset(t,0,sizeof(t));//开桶记录出现了几次。。。
for(int j = i;j <= block;j++)
{
k[i][j] = k[i][j-1];//k为在块 i ~ j中的众数
for(int z = l[j];z <= r[j];z++)
{
t[a[z]]++;
if(t[k[i][j]] < t[a[z]])
k[i][j] = a[z];
if(t[k[i][j]] == t[a[z]])
k[i][j] = min(k[i][j],a[z]);//暴力预处理
}
}
}
ans = 0;
for(int i = 1;i <= m;i++)
{
read(x);
read(y);
x = (x + ans - 1) % n + 1;
y = (y + ans - 1) % n + 1;//还原左右区间
if(x > y)
swap(x,y);
if(pos[x] - pos[y] <= 1)
in_block();//在同一块内暴力处理
else
out_block();//不同块分块处理
printf("%d\n",ans);
}
return 0;
}
```
by FutaRimeWoawaSete @ 2021-06-26 19:16:53
@我被JC了 你先把每类数离散化后按位置在 vector 里面存放，然后在暴力边角块的时候就可以在 vector 里面看现在这个值能不能在区间内装下超过最长的众数个数次个数，然后可以的话就继续往里面跳。
由于你边角块为 2 \sqrt n 个数，而你也处理了中间块的答案，所以用现在这个答案跳的话肯定是从后面那个边角块开始指的值，也就是说答案至多跳 \sqrt n 次，这样就可以保证时间复杂度了，你原来的代码我不清楚具体是哪里爆了，不过你预处理和查询的常数太大了，这么改常数会小很多。
给你放一下伪代码，这个是yuno3求区间众数出现次数的伪代码其实大同小异。
int Qry(int l,int r)
{
int LL = pos[l] , RR = pos[r];
if(LL == RR){int maxn = 0;for(int i = l ; i <= r ; i ++) bucket[a[i]] = 0;for(int i = l ; i <= r ; i ++){bucket[a[i]] ++ ; maxn = max(maxn , bucket[a[i]]);}return maxn;}
int Ans = F[LL + 1][RR - 1];
for(int i = l ; i <= R[LL] ; i ++){int lst = v[a[i]].size();while(pto[i] + Ans < lst && v[a[i]][pto[i] + Ans] <= r) Ans ++;}
for(int i = L[RR] ; i <= r ; i ++) while(pto[i] - Ans >= 0 && v[a[i]][pto[i] - Ans] >= l) Ans ++;
return Ans;
}