本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-24 17:33:27

思路

注意到给出的是一个排列，也就是每个数只会出现一次。所以如果枚举倍数或因数，总复杂度都是 $O(n\ln n)$ 的，这是本题复杂度正确的关键。

考虑对整个序列怎么做，设 $f_i$ 表示以 $i$ 为结尾的合法子序列数量，转移为 $f_i=\sum_{j=1}^{i-1}f_j[a_j\mid a_i]+1$，也就是在结尾是 $a_i$ 因数的子序列后接上 $a_i$，或 $a_i$ 自身作为一个子序列。

再扩展到区间询问。考虑把所有询问离线下来，然后从后往前依次处理整个序列，$f_i$ 也变成结尾为 $i$ 且开头已被处理的子序列数量。那么对于询问 $[l,r]$，只需要在处理完 $l$ 后计算 $\sum_{i=l}^r f_i$ 即为答案。

考虑如何计算 $a_i$ 对后面 $f$ 值的贡献。设 $d_j$ 表示 $f_j$ 在这一次维护中增多的数量，显然后面所有满足 $a_i\mid a_j$ 的 $f_j$ 都可以接在 $a_i$ 后面，也即 $d_j=1$。另外也可以从 $j$ 继续往后接上 $k$，需要满足 $a_j\mid a_k$。所以按照递增顺序依次处理每个 $j$，在处理完 $d_j$ 后给后面所有 $a_j\mid a_k$ 的 $d_k$ 加上 $d_j$，也就是在 $a_i$ 后面接上了一段子序列。

这样处理完所有 $d_j$ 后再全部加入 $f$ 数组即可。可以发现维护 $f$ 数组的过程是单点修改，同时会有对 $[l,r]$ 的区间查询，可以使用树状数组维护。时间复杂度为 $O(n\ln n(\ln n+\log n)+q \log n)$，分别为两重枚举倍数、单重枚举倍数修改和查询的复杂度。

代码

代码中预处理了 $tp_i$ 记录 $i$ 后面所有是 $a_i$ 倍数的位置。

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e6+10;
int n,q,d[N],a[N],pos[N],res[N]; 
vector <pii> ask[N]; 
vector <int> tp[N];
struct bit
{
	int b[N];
	void clear() {for(int i=0;i<=n;i++) b[i]=0;}
	int lowbit(int x) {return x&(-x);}
	void add(int p,int k) {for(;p<=n;p+=lowbit(p)) b[p]+=k;}
	int query(int p) {int tr=0; for(;p;p-=lowbit(p)) tr+=b[p]; return tr;}
}f;
void sol()
{
	cin>>n>>q,f.clear();
	for(int i=1;i<=n;i++) cin>>a[i],pos[a[i]]=i,ask[i].clear(),tp[i].clear();
	for(int i=1;i<=n;i++)
	{
		for(int j=a[i]*2;j<=n;j+=a[i]) if(pos[j]>i) tp[i].push_back(pos[j]);
		sort(tp[i].begin(),tp[i].end());
	}
	for(int i=1,l,r;i<=q;i++) cin>>l>>r,ask[l].push_back({r,i});
	for(int i=n;i>=1;i--)
	{
		f.add(i,1);
		for(int j:tp[i]) d[j]=1;
		for(int j:tp[i]) for(int k:tp[j]) d[k]+=d[j];
		for(int j:tp[i]) f.add(j,d[j]);
		for(pii te:ask[i]) res[te.second]=f.query(te.first);
	}
	for(int i=1;i<=q;i++) cout<<res[i]<<' ';
	cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TT; cin>>TT;
	while(TT--) sol();
	return 0;
}