题解 P4168 【[Violet]蒲公英】
zyzzyzzyzzyz
2018-12-11 19:34:54
------
## 分块
### 一.题意及思路
首先，发现题目是要求静态区间众数
**暴力**的想法:
先离散化,对于每个询问区间$[l,r]$ ,开一个桶,然后暴扫,复杂度$O(n\times m)$,TLE
那么可以考虑用线段树等
但是显然众数不满足区间可加性
所以考虑分块算法
虽然复杂度更劣，但代码简单
-----
### 二.分块正解
将整个区间分为$T$个块,每块长 $len$
那么询问$[l,r]$ 必然包括三个部分
即两端的零散区间和中间整段区间
那么众数的来源也就对应的只有三种情况
~~废话,不然呢!~~
到这里,我们的复杂度仍然是假的
因为每次都要将整个询问区间扫一遍
**那么此时分块的优势就体现出来了**
将询问区间分成三块后,分别处理:
1.左边零散区间:暴力扫,复杂度$O(len)$
2.右边零散区间:同上
**3.中间整块区间**:
我们可以预处理出一个数组$color[L][R][N]$做到每次询问时$O(1)$
**其中$L,R$是表示左右端点块(即当前区间$[l,r]=[L*len+1,R*len]$)**
$N$表示哪种颜色
那么$color[L][R][K]=color[L][R-1][K]+\sum_{i=(R-1)*len+1}^{R*len}[a[i]==K]$
所以预处理的复杂度是$O(N*T^2)$
那么总共的复杂度就是$O(N*T*T+M*N/T)$
可以发现当$T=N^\frac{1}{3}$ 时最优
### 三.代码
```cpp
#include<bits/stdc++.h>
#define il inline
#define RG register int
#define ll long long
#define gc getchar
using namespace std;
il int rd()
{
int x=0,flag=1;
char ch=0;
while((ch>'9'||ch<'0')&&ch!='-')ch=gc();
if(ch=='-')flag=-1,ch=gc();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return x*flag;
}
const int MAXT=40,MAXN=40010;
int color[MAXT][MAXT][MAXN];
int modenum[MAXT][MAXT],mdtimes[MAXT][MAXT];
int n,m,T,len;
int a[MAXN],b[MAXN];
int l,r,ans,ans2;
int main ()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
n=rd();m=rd();
T=floor(pow(n,0.3333333));
len=n/T;
for(RG i=1;i<=n;i++)
b[i]=a[i]=rd();
sort(b+1,b+n+1);
unique(b+1,b+n+1);
for(RG i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
for(RG i=1;i<=T;i++)
for(RG j=i;j<=T;j++){
for(RG k=1;k<=n;k++)
color[i][j][k]+=color[i][j-1][k];
for(RG k=(j-1)*len+1;k<=j*len;k++)
color[i][j][a[k]]++;
for(RG k=1;k<=n;k++)
if(mdtimes[i][j]<color[i][j][k])modenum[i][j]=k,mdtimes[i][j]=color[i][j][k];
}
for(RG i=1;i<=m;i++){
l=rd(),r=rd();
l=(l+b[ans2]-1)%n+1,r=(r+b[ans2]-1)%n+1;
if(l>r)swap(l,r);
int L=l/len+1,R=(r-1)/len;
ans2=modenum[L+1][R];//?
if(L<=R)
{
for(RG j=l;j<=L*len;j++)
color[L+1][R][a[j]]++;
for(RG j=R*len+1;j<=r;j++)
color[L+1][R][a[j]]++;
for(RG j=l;j<=L*len;j++)
if(color[L+1][R][a[j]]>color[L+1][R][ans2]||(color[L+1][R][a[j]]==color[L+1][R][ans2]&&ans2>a[j]))ans2=a[j];
for(RG j=R*len+1;j<=r;j++)
if(color[L+1][R][a[j]]>color[L+1][R][ans2]||(color[L+1][R][a[j]]==color[L+1][R][ans2]&&ans2>a[j]))ans2=a[j];
for(RG j=l;j<=L*len;j++)
color[L+1][R][a[j]]--;
for(RG j=R*len+1;j<=r;j++)
color[L+1][R][a[j]]--;
printf("%d\n",b[ans2]);
}
else
{
for(RG j=l;j<=r;j++)
color[L+1][R][a[j]]++;
for(RG j=l;j<=r;j++)
if(color[L+1][R][a[j]]>color[L+1][R][ans2]||(color[L+1][R][a[j]]==color[L+1][R][ans2]&&ans2>a[j]))ans2=a[j];
for(RG j=l;j<=r;j++)
color[L+1][R][a[j]]--;
printf("%d\n",b[ans2]);
}
}
return 0;
}
```