题解 P4168 【[Violet]蒲公英】
Leianha
2019-09-22 11:32:49
## 分块
提供几个必须要知道的注意事项。
首先暴力统计区间众数的时间复杂度为接近$O(n^2)$，时间复杂度不够优秀，所以我们 ~~遇事不决先分块~~考虑分段处理。数据范围比较大，所以我们离散化。所谓离散化就是将数据排好序后用ta的排名来代替ta本身（需要另开一个数组）。$nlog(n)$时间内就能完成。
```cpp
void yych()//离散化
{
len=sqrt(n);
memset(L,0x3f,sizeof(L));
for(int i=1;i<=n;++i)
{
pos[i]=(i-1)/len+1;
L[pos[i]]=min(L[pos[i]],i);
R[pos[i]]=max(R[pos[i]],i);
a[i]=read();
b[i]=a[i];
}
sort(b+1,b+1+n);
tot=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
}
```
然后我们考虑分块预处理。我们首先可以处理出每个数字在块中出现次数的前缀和。枚举每一个数是$O(n)$,枚举每一个块时间是$O(\sqrt n)$,所以总的时间就是$O(n \sqrt n)$。然后我们还可以处理出从第$l$个块到第$r$个块的区间众数。我们枚举$l$的复杂度是$O(\sqrt n)$,枚举$r$的复杂度是$O(\sqrt n)$,然后枚举块内每一个数的时间复杂度也是$O(\sqrt n)$,总共就是$O(n\sqrt n)$.
```cpp
void Treaker()//分块预处理
{
for(int i=1;i<=n;++i)
for(int j=pos[i];j<=pos[n];++j)s[j][a[i]]++;
for(int i=1;i<=pos[n];++i)
{
memset(tong,0,sizeof(tong));
for(int j=i;j<=pos[n];++j)
{
p[i][j]=p[i][j-1];
for(int k=L[j];k<=R[j];++k)
{
tong[a[k]]++;
if((tong[a[k]]>tong[p[i][j]])||(tong[a[k]]==tong[p[i][j]]&&a[k]<p[i][j]))p[i][j]=a[k];
}
}
}
memset(tong,0,sizeof(tong));
}
```
其中非常重要的就是
```cpp
p[i][j]=p[i][j-1];
```
因为我们首先需要继承原先的区间众数，然后才能够比较更新。否则的话就会 听取WA声一片,我就是有很多次挂在这里的 TAT.
然后就是询问操作，我们根据分块直觉，就应该是残块暴力搞，整块骚操作。所以我们对于$pos_r- pos_l \le2$的情况直接暴力就OK了。
```cpp
if(pos[r]-pos[l]<=2)
{
int res=0;
for(int i=l;i<=r;++i)
{
++tong[a[i]];
if(tong[a[i]]>tong[res]||(tong[a[i]]==tong[res]&&a[i]<res))res=a[i];
}
for(int i=l;i<=r;++i)tong[a[i]]=0;
return res;
}
```
对于其他的情况，我们知道我们所求的答案，要么是整块里的众数，要么是残块里的数字。对于残块里的数字，以为我们之前已经处理过了整块的数字出现的前缀和，所以我们能统计出残块中的数字在询问区间里的出现次数。对于整块中的众数，我们也能在$O(\sqrt n)$复杂度内统计出 ta在残块中的出现次数。这样我们就能得到我们询问区间里众数。
```cpp
int res=0;
for(int i=l;i<=R[pos[l]];++i)if(!tong[a[i]])tong[a[i]]+=s[pos[r]-1][a[i]]-s[pos[l]][a[i]];
for(int i=L[pos[r]];i<=r;++i)if(!tong[a[i]])tong[a[i]]+=s[pos[r]-1][a[i]]-s[pos[l]][a[i]];
for(int i=l;i<=R[pos[l]];++i)
{
++tong[a[i]];
if(tong[a[i]]>tong[res]||(tong[a[i]]==tong[res]&&a[i]<res))res=a[i];
}
for(int i=L[pos[r]];i<=r;++i)
{
++tong[a[i]];
if(tong[a[i]]>tong[res]||(tong[a[i]]==tong[res]&&a[i]<res))res=a[i];
}
int k=p[pos[l]+1][pos[r]-1];
int lin=s[pos[r]-1][k]-s[pos[l]][k];
for(int i=l;i<=R[pos[l]];++i)lin+=(a[i]==k);
for(int i=L[pos[r]];i<=r;++i)lin+=(a[i]==k);
if(lin>tong[res]||(lin==tong[res]&&k<res))res=k;
for(int i=l;i<=R[pos[l]];++i)tong[a[i]]=0;
for(int i=L[pos[r]];i<=r;++i)tong[a[i]]=0;
return res;
```
还有一点就是我们在统计每个数字出现的次数的时候我们需要开一个桶数组，我们每次用完了之后不用全部清空，只用将我们使用过的清空一下就珂以啦。实测可以省掉很大的时间。
最后说一下注意事项：
1.注意离散化，否则直接RE到原地起飞。
2.注意p数组的转移，否则WA到怀疑人生。
3.注意分块的边界，否则TLE到直接原地爆炸。
另外听说开$n^{\frac {1} {3}}$个块会更快一些，哪位大神能给窝解释解释?QAQ
最后献上窝丑陋的代码：
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,tot,len,l,r,ans;
const int N=40010,M=50010,K=510;
int a[N],b[N],pos[N],s[K][N],L[K],R[K],p[K][K],tong[N];
int read()
{
char ch;int x=0,f=1;
while(!isdigit(ch=getchar()))
{(ch=='-')&&(f=-f);}
while(isdigit(ch))
{x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int cnt=0;
void yych()//离散化
{
len=sqrt(n);
memset(L,0x3f,sizeof(L));
for(int i=1;i<=n;++i)
{
pos[i]=(i-1)/len+1;
L[pos[i]]=min(L[pos[i]],i);
R[pos[i]]=max(R[pos[i]],i);
a[i]=read();
b[i]=a[i];
}
sort(b+1,b+1+n);
tot=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
}
void Treaker()//分块预处理
{
for(int i=1;i<=n;++i)
for(int j=pos[i];j<=pos[n];++j)s[j][a[i]]++;
for(int i=1;i<=pos[n];++i)
{
memset(tong,0,sizeof(tong));
for(int j=i;j<=pos[n];++j)
{
p[i][j]=p[i][j-1];
for(int k=L[j];k<=R[j];++k)
{
tong[a[k]]++;
if((tong[a[k]]>tong[p[i][j]])||(tong[a[k]]==tong[p[i][j]]&&a[k]<p[i][j]))p[i][j]=a[k];
}
}
}
memset(tong,0,sizeof(tong));
}
int ask(int l,int r)
{
if(pos[r]-pos[l]<=2)
{
int res=0;
for(int i=l;i<=r;++i)
{
++tong[a[i]];
if(tong[a[i]]>tong[res]||(tong[a[i]]==tong[res]&&a[i]<res))res=a[i];
}
for(int i=l;i<=r;++i)tong[a[i]]=0;
return res;
}
int res=0;
for(int i=l;i<=R[pos[l]];++i)if(!tong[a[i]])tong[a[i]]+=s[pos[r]-1][a[i]]-s[pos[l]][a[i]];
for(int i=L[pos[r]];i<=r;++i)if(!tong[a[i]])tong[a[i]]+=s[pos[r]-1][a[i]]-s[pos[l]][a[i]];
for(int i=l;i<=R[pos[l]];++i)
{
++tong[a[i]];
if(tong[a[i]]>tong[res]||(tong[a[i]]==tong[res]&&a[i]<res))res=a[i];
}
for(int i=L[pos[r]];i<=r;++i)
{
++tong[a[i]];
if(tong[a[i]]>tong[res]||(tong[a[i]]==tong[res]&&a[i]<res))res=a[i];
}
int k=p[pos[l]+1][pos[r]-1];
int lin=s[pos[r]-1][k]-s[pos[l]][k];
for(int i=l;i<=R[pos[l]];++i)lin+=(a[i]==k);
for(int i=L[pos[r]];i<=r;++i)lin+=(a[i]==k);
if(lin>tong[res]||(lin==tong[res]&&k<res))res=k;
for(int i=l;i<=R[pos[l]];++i)tong[a[i]]=0;
for(int i=L[pos[r]];i<=r;++i)tong[a[i]]=0;
return res;
}
int main()
{
cin>>n>>m;
yych();
Treaker();
for(int i=1;i<=m;++i)
{
l=read();r=read();
l=(l+ans-1)%n+1;r=(r+ans-1)%n+1;
if(l>r)swap(l,r);
ans=b[ask(l,r)];
printf("%d\n",ans);
}
return 0;
}
/*
6 3
1 2 3 2 1 2
1 5
3 6
1 5
*/
```