[文章目录]
Description
所有蒲公英可以看成一个长度为n的序列a1~an，ai为一个正整数，表示第i颗蒲公英的种类编号。多次询问区间中出现最多的是那种蒲公英，次数相同输出编号最小的，强制在线。
真.分块第一题。
f[i][j]表示从第i块到第j块这个区间的答案，可以枚举i（√n个），用桶记录出现次数，预处理出来，复杂度n√n
g[i][j]表示第i中在前j个块中出现了多少次，预处理复杂度n√n
每次询问，将整块的答案拿出来，再将零散部分统计种类，会有√n种可能答案，找最优的即可。时间复杂度O(n√n+q√n)，空间n√n
貌似可以用外层维护区间，内层维护权值出现次数的树套树来解决此题。复杂度nlog^2n，空间nlog^2n
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 40100
int n,m,bl,a[N],b[N],c[N],tot;
int f[210][210],g[N][210],t[N],z[510];
int main()
{
scanf("%d%d",&n,&m);
int i; bl=(int)sqrt(n)+1;
for(i=0;i<n;++i) scanf("%d",a+i),b[i]=a[i];
sort(b,b+n);
for(c[tot++]=b[0],i=1;i<n;++i) if(b[i]!=b[i-1]) c[tot++]=b[i];
for(i=0;i<n;++i) a[i]=lower_bound(c,c+tot,a[i])-c;
int l,r,now;
for(l=0;l<n;l+=bl)
{
memset(t,0,sizeof t);
now=0; r=l+bl-1;
for(i=l;i<n;++i)
{
t[a[i]]++;
if(t[a[i]]>t[now]||(t[a[i]]==t[now]&&a[i]<now)) now=a[i];
if(i==r) f[l/bl][r/bl]=now,r+=bl;
}
}
memset(t,0,sizeof t);
for(l=0,r=bl-1;l<n;++l)
{
t[a[l]]++;
if(l==r)
{
for(i=0;i<tot;++i) g[i][l/bl]=t[i];
r+=bl;
}
}
memset(t,0,sizeof t);
int ans=0,L,R,top;
while(m--)
{
scanf("%d%d",&l,&r);
l=(l+ans-1)%n; r=(r+ans-1)%n;
if(l>r) swap(l,r);
if(r-l+1<=2*bl)
{
for(now=0,i=l;i<=r;++i)
{
t[a[i]]++;
if(t[a[i]]>t[now]|| (t[a[i]]==t[now]&&a[i]<now) ) now=a[i];
}
printf("%d\n",ans=c[now]);
for(i=l;i<=r;++i) t[a[i]]--;
}
else
{
top=0;
L= l%bl==0 ? l/bl : l/bl+1;
R= r%bl==bl-1 ? r/bl : r/bl-1;
for(i=l;i%bl!=0;++i)
{
if(!t[a[i]]) z[++top]=a[i];
t[a[i]]++;
}
for(i=r;i%bl!=bl-1;--i)
{
if(!t[a[i]]) z[++top]=a[i];
t[a[i]]++;
}
if(!t[f[L][R]]) z[++top]=f[L][R];
for(now=0,i=1;i<=top;++i)
{
t[z[i]]+=g[z[i]][R]-g[z[i]][L-1];
if(t[z[i]]>t[now]||(t[z[i]]==t[now]&&z[i]<now)) now=z[i];
}
printf("%d\n",ans=c[now]);
for(i=1;i<=top;++i) t[z[i]]=0;
}
}
return 0;
}