Part 1 简介
启发式分裂是一种基于启发式合并思想的分治。
通常应用于:
- 统计所有区间 的有关区间内某个代表元(极值、不合法的位置)的贡献;
注意 的代表元 需要满足 , 是 的代表元,例如极值就满足这个性质。请注意同一个区间的代表元可能有多个。
做题时一般较难想到,需要注意一下可以往这方面想。
Part 2 算法流程
考虑当前分治区间 ,显然可以:
- 遍历一次区间找到代表元 ;
- 处理 的 的贡献;
- 分治处理 和 ;
但是这样做的时间复杂度最劣是 的,考虑类似 meet-in-middle 的思想:
- 从左右两端同时往中间遍历区间 / 预处理,找到代表元 ;
- 处理 的 的贡献:
- 若 ,即 更短,则枚举 ,快速计算所有 的贡献和 / 对 的影响;
- 否则枚举 ,快速计算所有 的贡献和 / 对 的影响;
- 分治处理 和 ;
这样做的本质可以看做在 dfs 树上启发式合并,时间复杂度 。
有些时候需要注意分治处理时左右区间的顺序。
Part 3 例题
3.1 P4755 Beautiful Pair
小 D 有个数列 ,当一个数对 ()满足 和 的积不大于 中的最大值时,小 D 认为这个数对是美丽的。请你求出美丽的数对的数量。
,。
题解
启发式分裂,先离散化,在处理 前把所有 扔进树状数组里。
处理 时:
- 若 ,直接返回;
- 若 ,在树状数组中删除 并返回;
- 预处理 ST 表快速找到 中最大值的位置 ;
- 处理 的 的贡献:
- 若 :
- 在树状数组中删除 ;
- 遍历 ,算出树状数组中 的数的个数 ,令答案增加 ;
- 在树状数组中删除 ;
- 分治处理 ,注意处理后树状数组中的 已经被删除;
- 在树状数组中加入 并分治处理 ;
- 否则枚举 ,处理方法类似,注意要先分治处理 ;
时间复杂度 ,代码如下:
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int S=100005,BS=25; int n,a[S]; int m,b[S]; int mlog[S],mx[S][BS]; int c[S]; long long ans; inline int que(int l,int r) { int k=mlog[r-l+1]; int x=mx[l][k],y=mx[r-(1<<k)+1][k]; return a[x]>a[y]?x:y; } inline void addtr(int pos,int val) { for(int i=pos;i<=m;i+=i&-i) c[i]+=val; } inline int quetr(int pos) { int res=0; for(int i=pos;i>=1;i-=i&-i) res+=c[i]; return res; } void slove(int l,int r) { if(l>r) return; if(l==r) return ans+=b[a[l]]==1,addtr(a[l],-1),void(); int x=que(l,r); if(x-l+1<r-x+1) { for(int i=l;i<=x-1;i++) addtr(a[i],-1); for(int i=l;i<=x;i++) { int p=upper_bound(b+1,b+m+1,b[a[x]]/b[a[i]])-b-1; ans+=quetr(p); } addtr(a[x],-1); slove(x+1,r); for(int i=l;i<=x-1;i++) addtr(a[i],1); slove(l,x-1); } else { for(int i=x+1;i<=r;i++) addtr(a[i],-1); for(int i=x;i<=r;i++) { int p=upper_bound(b+1,b+m+1,b[a[x]]/b[a[i]])-b-1; ans+=quetr(p); } addtr(a[x],-1); slove(l,x-1); for(int i=x+1;i<=r;i++) addtr(a[i],1); slove(x+1,r); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[++m]=a[i]; sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1; for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b; mlog[0]=-1; for(int i=1;i<=n;i++) mlog[i]=mlog[i>>1]+1,mx[i][0]=i; for(int j=1;j<=BS-3;j++) { for(int i=1;i<=n-(1<<j)+1;i++) { int x=mx[i][j-1],y=mx[i+(1<<j-1)][j-1]; mx[i][j]=a[x]>a[y]?x:y; } } for(int i=1;i<=n;i++) addtr(a[i],1); slove(1,n); printf("%lld\n",ans); return 0; }
3.2 LOJ6198 谢特
给定一个长 的字符串 和 个整数 ,定义二元组 ()的权值为 ,其中 为按位异或运算。对于所有 (),求出最大的权值。
,。
题解
如果不往启发式分裂这方面想是挺难想到的。
相当于跑 SA 之后的 ,即某个区间中的最小值,而最大异或又很好维护,所以直接 SA + trie + 启发式分裂即可。
时间复杂度 。