2019-12-25
题意
给定一个含有n个数(1<=n<=4e4)的序列，保证每个数都小于1e9，给定m个询问(1<=m<=5e4），每次询问给定一个区间[l,r]，求区间众数，若有多个众数，则输出最小的一个。注意：题目有lastans，要求强制在线
题解
首先先将序列离散化（废话）。注意到n,m都只有不到1e5的规模，容易想到分块系的做法（n的3/2次或5/3次）。但是区间众数这个东西既不满足区间减、只满足区间加，而区间加又是暴力的O(n)，因此不可能用传统分块进行维护。因此考虑到我们将每个块的左右端点两两进行匹配视为不同的区间（即每个块的左端点与所有其右侧的块的右端点都视为不同的区间），暴力的算出每个区间的每个数的出现情况和区间众数。每次找到最近的块进行扩展和查询，查询完毕后再还原即可。接下来要考虑的问题是块的大小。不妨设共有x个块。则预处理部分的复杂度是O(n×k2)，询问部分的复杂度是O（nm/k）的。很明显，当预处理和查询的复杂度接近时，时间复杂度最小。由于n,m大小相仿，不妨设其复杂度统计，则解方程n×k2=nm/k，解得k=n1/3。所以每个块的大小为n2/3最合适，整个代码的复杂度大约是O(n^5/3)，大约在7e7的样子，刚好卡线过。（其实常数蛮大的，最慢的要1.01s，要不是时限是2s就扑街了）
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()//快读
{
int ret=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return w*ret;
}
int n,m;
int a[40010];//原数组
int b[40010];//离散化用数组
map<int,int> mp,mp2;//正向+反向离散化
int t,tot;//t为块大小，tot为块的数目
struct node{
int type[40010];
int maxn;
}f[1510];//保存每个区间的信息
int pos[40010];//所在块编号
inline void prework()//预处理
{
int cnt=0;
for(int i=1;i<=n;i++)
if(!mp[b[i]]) mp[b[i]]=++cnt,mp2[cnt]=b[i];
for(int i=1;i<=n;i++) a[i]=mp[a[i]];
t=pow(n,2.0/3.0);
tot=n/t;//计算块的大小和块的数量
if(tot*t<n) tot++;
for(int i=1;i<=tot;i++)//预处理所有的区间的每个数出现次数以及众数
for(int j=i;j<=tot;j++)
{
int lp=(i-1)*t+1,rp=min(j*t,n);//确定左右端点
int p=i*(tot+1)+j;//
for(int k=lp;k<=rp;k++)//暴力计算区间信息
{
f[p].type[a[k]]++;
if(f[p].type[a[k]]>f[p].type[f[p].maxn]||(f[p].type[a[k]]==f[p].type[f[p].maxn]&&f[p].maxn>a[k])) f[p].maxn=a[k];
}
}
for(int i=1;i<=n;i++) pos[i]=(i-1)/t+1;//计算pos数组
}
inline int solve(int l,int r)//查询
{
int lp=pos[l],rp=pos[r];
int p,tmp=0;
if(lp==rp||lp+1==rp)//若所在块相同或相邻，则无完整的区间信息可以调用，直接一个个计算即可
{
p=0;
for(int i=l;i<=r;i++)
{
f[p].type[a[i]]++;
if(f[p].type[a[i]]>f[p].type[f[p].maxn]||(f[p].type[a[i]]==f[p].type[f[p].maxn]&&f[p].maxn>a[i])) f[p].maxn=a[i];
}
int ans=f[p].maxn;
for(int i=l;i<=r;i++) f[p].type[a[i]]--;
f[p].maxn=0;
return ans;
}
lp++,rp--;//否则lp和rp中间的部分是完整的块，找到合适的区间信息并以此为基础扩展
p=lp*(tot+1)+rp,tmp=f[p].maxn;
for(int i=l;i<=(lp-1)*t;i++)//统计块左部分
{
f[p].type[a[i]]++;
if(f[p].type[a[i]]>f[p].type[f[p].maxn]||(f[p].type[a[i]]==f[p].type[f[p].maxn]&&f[p].maxn>a[i])) f[p].maxn=a[i];
}
for(int i=rp*t+1;i<=r;i++)//统计块右部分
{
f[p].type[a[i]]++;
if(f[p].type[a[i]]>f[p].type[f[p].maxn]||(f[p].type[a[i]]==f[p].type[f[p].maxn]&&f[p].maxn>a[i])) f[p].maxn=a[i];
}
int ans=f[p].maxn;//计算答案
for(int i=l;i<=(lp-1)*t;i++) f[p].type[a[i]]--;//还原现场
for(int i=rp*t+1;i<=r;i++) f[p].type[a[i]]--;
f[p].maxn=tmp;
return ans;
}
int lastans=0;
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
sort(b+1,b+n+1);
prework();
for(int i=1;i<=m;i++)
{
int l=read(),r=read();
l=(l+lastans-1)%n+1,r=(r+lastans-1)%n+1;//记得计算lastans
if(l>r) swap(l,r);
lastans=mp2[solve(l,r)];//此处要注意！！！lastans所保存的答案是原数组中的数而非离散化后的
printf("%d\n",lastans);
}
return 0;
}
后记
这道题本来应该30min就A的，结果因为各种愚蠢的锅而跟傻子一样调了好久。最后就因为lastans存了离散化后的答案而差点自闭QAQ比较可惜的是这道题黑掉紫了，否则就做出了人生第一道黑体了啊……最后祝大家圣诞节快乐o(╥﹏╥)o