P4168 [Violet]蒲公英(分块)
题意
考虑这种题必定是需要桶+分块的
做法一：
设块长为T,预处理：
c[i][j][k]表示块i到块j中编号为k的数出现的次数
ans[i][j]表示块i到块j中的众数
pos[i][j]表示块i到块j中的众数的编号
考虑答案只可能为如下两种：整块内的众数,散块内的数,暴力维护即可
复杂度:
1.预处理:NT^2
2.求解：M*N/T (N/T即为块长)
根据均值不等式:NT^2=M*N/T时取最小值:T=pow(N,1/3)
code：
#include<bits/stdc++.h>
using namespace std;
const int maxn=40010;
const int maxt=40;
int n,m,t,len,cnt,lastans,res,num,lp,rp;
int a[maxn],b[maxn],L[maxt],R[maxt];
int ans[maxt][maxt],pos[maxt][maxt];
int c[maxt][maxt][maxn];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
inline void up(int i)
{
c[lp][rp][a[i]]++;
if(c[lp][rp][a[i]]>res||(c[lp][rp][a[i]]==res&&a[i]<num))res=c[lp][rp][a[i]],num=a[i];
}
inline int solve(int x,int y)
{
int l,r;
for(int i=1;i<=t;i++)if(x<=R[i]){l=i;break;}
for(int i=t;i;i--)if(y>=L[i]){r=i;break;}
if(l+1<=r-1)lp=l+1,rp=r-1;
else lp=rp=0;
res=ans[lp][rp],num=pos[lp][rp];
if(l==r)
{
for(int i=x;i<=y;i++)up(i);
for(int i=x;i<=y;i++)c[lp][rp][a[i]]--;
}
else
{
for(int i=x;i<=R[l];i++)up(i);
for(int i=L[r];i<=y;i++)up(i);
for(int i=x;i<=R[l];i++)c[lp][rp][a[i]]--;
for(int i=L[r];i<=y;i++)c[lp][rp][a[i]]--;
}
return b[num];
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=b[i]=read();
t=(int)pow(n*1.0,1.0/3.0);
if(t)len=n/t;
for(int i=1;i<=t;i++)L[i]=(i-1)*len+1,R[i]=i*len;
if(R[t]<n)L[t+1]=R[t]+1,R[++t]=n;
sort(b+1,b+n+1);cnt=unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
for(int i=1;i<=t;i++)
for(int j=1;j<=t;j++)
{
for(int k=L[i];k<=R[j];k++)c[i][j][a[k]]++;
for(int k=1;k<=cnt;k++)
if(c[i][j][k]>ans[i][j]||(c[i][j][k]==ans[i][j]&&k<pos[i][j]))
ans[i][j]=c[i][j][k],pos[i][j]=k;
}
for(int i=1;i<=m;i++)
{
int x=(read()+lastans-1)%n+1,y=(read()+lastans-1)%n+1;
if(x>y)swap(x,y);
printf("%d\n",lastans=solve(x,y));
}
return 0;
}做法二:
就是做法一的改进版,我们有一个很巧妙的方法,能过O(logN)求出一个数在一个区间中出现的次数:
对每个数开个vector,因此记录每个数出现的位置,显然是有序的,假设要求[l,r]中x出现的次数,在vector中二分第一个>=l的位置和最后一个<=r的位置,做差即可求出x在[l,r]中出现的次数
code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=40010;
const int maxt=1010;
int n,m,t,len,cnt,lastans;
int a[maxn],b[maxn],L[maxt],R[maxt],pos[maxn],sum[maxn];
int f[maxt][maxt];
vector<int>c[maxn];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
inline void work(int x)
{
memset(sum,0,sizeof(sum));
int maxx=0,num=0;
for(int i=L[x];i<=n;i++)
{
sum[a[i]]++;
if(maxx<sum[a[i]]||(maxx==sum[a[i]]&&b[a[i]]<b[num]))maxx=sum[a[i]],num=a[i];
f[x][pos[i]]=num;
}
}
inline int calc(int ql,int qr,int k)
{
return upper_bound(c[k].begin(),c[k].end(),qr)-lower_bound(c[k].begin(),c[k].end(),ql);
}
inline int query(int x,int y)
{
int l=pos[x],r=pos[y];
if(l+1>=r-1)
{
int maxx=0,num=0;
for(int i=x;i<=y;i++)
{
int tmp=calc(x,y,a[i]);
if(maxx<tmp||(maxx==tmp&&b[a[i]]<b[num]))maxx=tmp,num=a[i];
}
return b[num];
}
int num=f[l+1][r-1],maxx=calc(x,y,f[l+1][r-1]);
for(int i=x;i<=R[l];i++)
{
int tmp=calc(x,y,a[i]);
if(maxx<tmp||(maxx==tmp&&b[a[i]]<b[num]))maxx=tmp,num=a[i];
}
for(int i=L[r];i<=y;i++)
{
int tmp=calc(x,y,a[i]);
if(maxx<tmp||(maxx==tmp&&b[a[i]]<b[num]))maxx=tmp,num=a[i];
}
return b[num];
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)b[i]=a[i]=read();
t=sqrt(n*log(n));len=n/t;
for(int i=1;i<=t;i++)L[i]=(i-1)*len+1,R[i]=i*len;
if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
for(int i=1;i<=t;i++)
for(int j=L[i];j<=R[i];j++)
pos[j]=i;
sort(b+1,b+n+1);cnt=unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
for(int i=1;i<=n;i++)c[a[i]].push_back(i);
for(int i=1;i<=t;i++)work(i);
for(int i=1;i<=m;i++)
{
int x=(read()+lastans-1)%n+1,y=(read()+lastans-1)%n+1;
if(x>y)swap(x,y);
printf("%d\n",lastans=query(x,y));
}
return 0;
}