前言
“***，你会四毛子算法吗？不会的话就去学会，给同学们讲讲”
简介
四毛子算法 (Four Russian) 是一个由四位俄罗斯人毛子提出的一种可以在 $O(n \log \log n) - O(1)$ 复杂度内解决RMQ问题的算法。
算法流程
首先把序列分块，对于每块内部维护一个ST表，对于不同的块之间再维护一个ST表。
每次查询一个 $[l,r]$ 的时候:
假设l所在的区间为 $[l_1,r_1]$ ，r所在的区间为 $[l_2,r_2]$。
若l和r处于同一块内，直接查询块内的ST表即可。
若l和r处于相邻块内，则直接查询 $[l,r_1]$ 和 $[l_2,r]$ 的最小值即可。
否则，我们把区间 $[l,r]$ 分成三段：
1: $[l,r_1]$
2: $[r_1+1,l_2-1]$
3: $[l_2,r]$
其中第二个区间直接查询不同块之间的ST表，第一个和第三个区间块内查询即可。
复杂度分析
查询复杂度显然为 $O(1)$。
设块长为k，则有预处理复杂度：
$$O(\frac{n}{k} \log \frac{n}{k}+n \log k)$$
我们取 $k=\log n$ ，就得到了复杂度 $O(n \log \log n)$ 。
空间复杂度也为 $O(n \log \log n)$ 。
算法改进
我们发现原版四毛子算法的常数非常大，因为每次询问可能要跑3个ST表。
考虑改进这个过程。我们发现块内查询相当于查询前缀/后缀最小值，所以我们在预处理的过程中，对于每个块暴力预处理出它们的前缀和后缀min。这样询问只需要跑一个ST表，常数大大减小。
代码
真不难写(逃
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
| #include<bits/stdc++.h>
using namespace std;
int n,m,blo,tot,lc[1000005],rc[1000005],bel[1000005],a[1000005],log1[1000005];
inline void init(){
log1[1]=0;
for(int i=2;i<=1000000;++i)log1[i]=log1[i>>1]+1;
blo=log1[n];
for(int i=1;i*blo<=n;++i)lc[++tot]=blo*(i-1)+1,rc[tot]=blo*i;
if(n%blo){
int tmp=n/blo;
lc[++tot]=tmp*blo+1,rc[tot]=n;
}
for(int i=1;i<=tot;++i)
for(int j=lc[i];j<=rc[i];++j)bel[j]=i;
}
struct stable{
int f[18][18],lf[18],rf[18],len;
void init(int l,int r){
len=r-l+1;
memset(lf,0x3f,sizeof lf);
memset(rf,0x3f,sizeof rf);
for(int i=1;i<=len;++i)f[i][0]=a[l+i-1];
for(int j=1;(1<<j)<=len;++j)
for(int i=1;i+(1<<j)-1<=len;++i)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
for(int i=1;i<=len;++i)lf[i]=min(lf[i-1],f[i][0]);
for(int i=len;i>=1;--i)rf[i]=min(rf[i+1],f[i][0]);
}
inline int askm(int l,int r){
int x=log1[r-l+1];
return min(f[l][x],f[r-(1<<x)+1][x]);
}
inline int askl(int r){return lf[r];}
inline int askr(int l){return rf[l];}
inline int ask(int l,int r){
if(l<1||r>len||l>r)return -1;
if(l==1)return askl(r);
else if(r==len)return askr(l);
else return askm(l,r);
}
};
struct st_table{
stable s[100005];
int len,f[100005][25];
void init(int n){
len=tot;
for(int i=1;i<=len;++i)s[i].init(lc[i],rc[i]);
for(int i=1;i<=len;++i)f[i][0]=s[i].ask(1,s[i].len);
for(int j=1;(1<<j)<=len;++j)
for(int i=1;i+(1<<j)-1<=len;++i)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int ask(int l,int r){
int x=bel[l],y=bel[r],z=log1[y-x-1],ansl=1e9,ansr;
if(x==y)return s[x].ask(l-lc[x]+1,r-lc[x]+1);
if(x!=y-1)ansl=min(f[x+1][z],f[y-(1<<z)][z]);
ansr=min(s[x].ask(l+s[x].len-rc[x],s[x].len),s[y].ask(1,r-lc[y]+1));
return min(ansl,ansr);
}
}s;
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;init();
for(int i=1;i<=n;++i)cin>>a[i];
s.init(n);
for(int i=1;i<=m;++i){
int l,r;cin>>l>>r;
cout<<s.ask(l,r)<<'\n';
}
return 0;
}
|
提示
请注意，该四毛子算法常数仍然巨大，不保证可以通过模板题(但是loj的过了而且比ST表快
