启发式分裂 学习笔记

Part 1 简介

启发式分裂是一种基于启发式合并思想的分治。

通常应用于:

  • 统计所有区间 [i,j][i,j] 的有关区间内某个代表元(极值、不合法的位置)的贡献;

注意 [l,r][l,r] 的代表元 xx 需要满足 x[l,r][l,r]\forall x\in [l',r']\in [l,r]xx[l,r][l',r'] 的代表元,例如极值就满足这个性质。请注意同一个区间的代表元可能有多个

做题时一般较难想到,需要注意一下可以往这方面想。

Part 2 算法流程

考虑当前分治区间 [l,r][l,r],显然可以:

  1. 遍历一次区间找到代表元 xx
  2. 处理 l[l,x],r[x,r]l'\in [l,x],r'\in [x,r][l,r][l',r'] 的贡献;
  3. 分治处理 [l,x1][l,x-1][x+1,r][x+1,r]

但是这样做的时间复杂度最劣是 O(n2)O(n^2) 的,考虑类似 meet-in-middle 的思想:

  1. 从左右两端同时往中间遍历区间 / 预处理,找到代表元 xx
  2. 处理 l[l,x],r[x,r]l'\in [l,x],r'\in [x,r][l,r][l',r'] 的贡献:
    • xl+1<rx+1x-l+1<r-x+1,即 [l,x][l,x] 更短,则枚举 ll',快速计算所有 rr' 的贡献和 / 对 [x+1,r][x+1,r] 的影响;
    • 否则枚举 rr',快速计算所有 ll' 的贡献和 / 对 [l,x1][l,x-1] 的影响;
  3. 分治处理 [l,x1][l,x-1][x+1,r][x+1,r]

这样做的本质可以看做在 dfs 树上启发式合并,时间复杂度 O(nlogn)O(n\log n)

有些时候需要注意分治处理时左右区间的顺序。

Part 3 例题

3.1 P4755 Beautiful Pair

小 D 有个数列 {a}\{a\},当一个数对 (i,j)(i,j)iji \le j)满足 aia_iaja_j 的积不大于 ai,ai+1,,aja_i, a_{i+1}, \ldots, a_j 中的最大值时,小 D 认为这个数对是美丽的。请你求出美丽的数对的数量。

1n1051\le n\le{10}^51ai1091\le a_i\le{10}^9

题解

启发式分裂,先离散化,在处理 [1,n][1,n] 前把所有 aia_i 扔进树状数组里。

处理 [l,r][l,r] 时:

  1. l>rl>r,直接返回;
  2. l=rl=r,在树状数组中删除 ala_l 并返回;
  3. 预处理 ST 表快速找到 [l,r][l,r] 中最大值的位置 xx;
  4. 处理 l[l,x],r[x,r]l'\in [l,x],r'\in [x,r][l,r][l',r'] 的贡献:
    • xl+1<rx+1x-l+1<r-x+1
      1. 在树状数组中删除 a[l,x1]a_{[l,x-1]}
      2. 遍历 l[l,x]l'\in [l,x],算出树状数组中 axal\le \lfloor\frac{a_x}{a_{l'}}\rfloor 的数的个数 cntcnt,令答案增加 cntcnt
      3. 在树状数组中删除 axa_{x}
      4. 分治处理 [x+1,r][x+1,r],注意处理后树状数组中的 a[x+1,r]a_{[x+1,r]} 已经被删除;
      5. 在树状数组中加入 a[l,x1]a_{[l,x-1]} 并分治处理 [l,x1][l,x-1]
    • 否则枚举 rr',处理方法类似,注意要先分治处理 [l,x1][l,x-1]

时间复杂度 O(nlog2n)O(n\log^2 n),代码如下:

#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 谢特

给定一个长 nn 的字符串 SSnn 个整数 wiw_i,定义二元组 (i,j)(i,j)i=ji\not=j)的权值为 LCP(S[i,n],S[j,n])+(wiwj)\text{LCP}(S_{[i,n]},S_{[j,n]})+(w_i\oplus w_j),其中 \oplus 为按位异或运算。对于所有 (i,j)(i,j)i=ji\not=j),求出最大的权值。

1n1051\le n\le 10^50wi<n0\le w_i<n

题解

如果不往启发式分裂这方面想是挺难想到的。

LCP(S[i,n],S[j,n])\text{LCP}(S_{[i,n]},S_{[j,n]}) 相当于跑 SA 之后的 mink=rkirkj1heightk\min\limits_{k=rk_i}^{rk_j-1}height_k,即某个区间中的最小值,而最大异或又很好维护,所以直接 SA + trie + 启发式分裂即可。

时间复杂度 O(nlog2n)O(n\log^2 n)

3.3 【2023NOIP模拟赛06】我是 C 题