CF1946F 题解

KSCD_ · 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;
}