隐藏
「bsoj3540」蒲公英 - 分块 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj3540」蒲公英 - 分块

题目大意

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


题目分析

此题可以似乎使用树套树,但是分块更加方便。

本人对分块很有研究,以后找时间详细讲讲分块的黑科技。

对于本题,我们可以将序列分为$\sqrt n$个块,并预处理$f[i,j]$表示块$i$与$j$之间的答案。

因为我们发现两个块的答案是不方便进行快速合并的,因此考虑直接递推,用指针$pos$从块$i$的最左端扫描到$n$,并更新$Hash$表,更新相应的$f[i,j]$。
这样我们可以在$O(n\sqrt n)$的时间内预处理出$f[i,j]$。

接下来考虑询问。

我们将询问分为整块的答案与两边零散的点。
先将答案初始化为$f[L+1,R-1]$。
接着从$x$扫描到$L$的右端点,从$R$的左端点扫描到$y$,利用$x\rightarrow y$中当前颜色的出现次数统计答案。

接下来问题转化为求$x\rightarrow y$每个颜色的出现次数。

  • 方法一(网上普遍做法):时间复杂度$O(n\sqrt n\log n)$
    利用链表将每种颜色的点串起来,用两次二分即可找到每种颜色出现次数。

  • 方法二:时间复杂度$O(n\sqrt n)$,空间复杂度$O(n\sqrt n)$
    $O(n\sqrt n)$预处理每个块中每种颜色的出现次数$Hash[x,color]$,并对$Hash$作前缀和$sum[x,color]$。
    统计出$x\rightarrow Right[L],Left[R]\rightarrow y$每个颜色的出现次数。
    这样就可以$O(1)$得到出现次数了。


代码

方法二

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
92
93
94
95
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=40005,maxb=205;
int n,m,BCC=0,Belong[maxn],a[maxn],b[maxn],f[maxb][maxb],Hash[maxb][maxn],sum[maxb][maxn],Left[maxb],Right[maxb];

map<int,int>M,fM;
void Discretization() {
for(int i=1; i<=n; i++)M[a[i]]=1;
int i=1;
for(auto it=M.begin(); it!=M.end(); it++,i++)it->second=i;
for(int i=1; i<=n; i++)b[i]=M[a[i]],fM[b[i]]=a[i];
}

int Query(int x,int y) {
int L=Belong[x],R=Belong[y];
if(R-L<=1) {
int tmphash[maxn]= {0},Ans=0;
for(int i=x; i<=y; i++) {
tmphash[b[i]]++;
if(tmphash[b[i]]>tmphash[Ans]||(tmphash[b[i]]==tmphash[Ans]&&b[i]<Ans))Ans=b[i];
}
return fM[Ans];
}
int LHash[maxn]= {0},RHash[maxn]= {0};
for(int i=x; i<=Right[L]; i++)LHash[b[i]]++;
for(int i=Left[R]; i<=y; i++)RHash[b[i]]++;
int Ans=f[L+1][R-1];
for(int i=x; i<=Right[L]; i++) {
int now=LHash[b[i]]+RHash[b[i]]+sum[R-1][b[i]]-sum[L][b[i]],last=LHash[Ans]+RHash[Ans]+sum[R-1][Ans]-sum[L][Ans];
if(now>last||(now==last&&b[i]<Ans))Ans=b[i];
}
for(int i=Left[R]; i<=y; i++) {
int now=LHash[b[i]]+RHash[b[i]]+sum[R-1][b[i]]-sum[L][b[i]],last=LHash[Ans]+RHash[Ans]+sum[R-1][Ans]-sum[L][Ans];
if(now>last||(now==last&&b[i]<Ans))Ans=b[i];
}
return fM[Ans];
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
Discretization();
int size=sqrt(n);
for(int i=1; i<=n; i++)Belong[i]=(i-1)/size+1;
for(int i=1; i<=n; i++) {
if(!Left[Belong[i]])Left[Belong[i]]=i,BCC++;
Right[Belong[i]]=i;
}
for(int i=1; i<=BCC; i++)
for(int j=Left[i]; j<=Right[i]; j++)
Hash[i][b[j]]++;
for(int i=1; i<=BCC; i++)
for(int j=1; j<=n; j++)sum[i][j]=sum[i-1][j]+Hash[i][j];
for(int i=1; i<=BCC; i++) {
int tmphash[maxn]= {0};
for(int j=Left[i]; j<=n; j++) {
tmphash[b[j]]++;
f[i][Belong[j]]=f[i][Belong[j-1]];
if(tmphash[b[j]]>tmphash[f[i][Belong[j]]]||(tmphash[b[j]]==tmphash[f[i][Belong[j]]]&&b[j]<f[i][Belong[j]]))f[i][Belong[j]]=b[j];
}
}
int lastans=0;
for(int i=1; i<=m; i++) {
int x=(Get_Int()+lastans-1)%n+1,y=(Get_Int()+lastans-1)%n+1;
if(x>y)swap(x,y);
lastans=Query(x,y);
printf("%d\n",lastans);
}
return 0;
}

姥爷们赏瓶冰阔落吧~