BZOJ2724 蒲公英

题意

在乡下的小路旁种着许多蒲公英,而我们的问题正是与这些蒲公英有关。
为了简化起见,我们把所有的蒲公英看成一个长度为$n$的序列$(a_1,a_2…a_n)$,其中$a_i$为一个正整数,表示第$i$棵蒲公英的种类编号。
共有$m$次询问,每次询问一个区间$[l,r]$,你需要回答区间里出现次数最多的是哪种蒲公英,如果有若干种蒲公英出现次数相同,则输出种类编号最小的那个。
注意,你的算法必须是在线的。
$1 \leqslant n \leqslant 40000,1 \leqslant m \leqslant 50000$。

题解

几万的范围容易让人想到各种根号算法,这里我们使用分块来解决。先将序列分为$\sqrt{n}$个块,再预处理出在每个块的末端这个位置上的各种颜色的前缀和,以及第$i$个块到第$j$个块的答案。处理询问的时候,我们在遇到边角料的一个颜色之后,就将其颜色个数修改一下,并与答案chkmax一下即可。最后记得把颜色数改回来就好。
时间复杂度$O(n\sqrt{n})$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=4e4+10;
const int maxblk=2e2+10;
int a[maxn],val[maxn],beg[maxn],end[maxn],pos[maxn],sum[maxblk][maxn],ans[maxblk][maxblk],tmp[maxn];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
int i,j,k,n,q;
#ifndef ONLINE_JUDGE
freopen("BZOJ2724.in","r",stdin);
freopen("BZOJ2724.out","w",stdout);
#endif
n=read();q=read();
int blocksz=(int)sqrt(n),cnt=0;
for(i=1;i<=n;i++){
a[i]=val[i]=read();
if(i%blocksz==0 || i==n)end[cnt]=i;
if(i%blocksz==1)beg[++cnt]=i;
pos[i]=cnt;
}
sort(val+1,val+n+1);
int Sum=unique(val+1,val+n+1)-val-1;
for(i=1;i<=n;i++)a[i]=lower_bound(val+1,val+Sum+1,a[i])-val;
for(i=1;i<=cnt;i++){
memcpy(sum[i],sum[i-1],sizeof(sum[i]));
for(j=beg[i];j<=end[i];j++)
sum[i][a[j]]++;
}
for(i=1;i<=cnt;i++){
for(j=i;j<=cnt;j++){
ans[i][j]=ans[i][j-1];
for(k=beg[j];k<=end[j];k++){
tmp[a[k]]++;
if(tmp[a[k]]>tmp[ans[i][j]] || (tmp[a[k]]==tmp[ans[i][j]] && a[k]<ans[i][j]))
ans[i][j]=a[k];
}
}
memset(tmp,0,sizeof(tmp));
}
int lans=0;
while(q--){
int l=read(),r=read();
l=(l+lans-1)%n+1;r=(r+lans-1)%n+1;
if(l>r)swap(l,r);
int x=pos[l],y=pos[r];
int id,Max=0;
if(y-x<=1){
for(i=l;i<=r;i++){
tmp[a[i]]++;
if(tmp[a[i]]>Max || (tmp[a[i]]==Max && val[a[i]]<val[id])){
id=a[i];Max=tmp[a[i]];
}
}
printf("%d\n",val[id]);lans=val[id];
for(i=l;i<=r;i++)tmp[a[i]]--;
continue;
}
id=ans[x+1][y-1];Max=sum[y-1][id]-sum[x][id];
for(i=l;i<=end[x];i++){
sum[x][a[i]]--;
if(sum[y-1][a[i]]-sum[x][a[i]]>Max || (sum[y-1][a[i]]-sum[x][a[i]]==Max && a[i]<id)){
id=a[i];Max=sum[y-1][a[i]]-sum[x][a[i]];
}
}
for(i=beg[y];i<=r;i++){
sum[y-1][a[i]]++;
if(sum[y-1][a[i]]-sum[x][a[i]]>Max || (sum[y-1][a[i]]-sum[x][a[i]]==Max && a[i]<id)){
id=a[i];Max=sum[y-1][a[i]]-sum[x][a[i]];
}
}
printf("%d\n",val[id]);lans=val[id];
for(i=l;i<=end[x];i++)sum[x][a[i]]++;
for(i=beg[y];i<=r;i++)sum[y-1][a[i]]--;
}
return 0;
}