启发式分裂 学习笔记

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

处理 $[l,r]$ 时：

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

时间复杂度 $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;
}

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

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

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