题解：CF1946F Nobody is needed

· · 题解

传送门

好题！我调了一下午。注意维护区间和不能用线段树，常数过大会超时，只能用树状数组。记得多测要清空。

首先可以证明在长度为 n 的全排列中只有 n\log n 个子区间 [a_l,a_r] 满足 a_l\mid a_r。

设 f_i 为以 a_i 为区间右端点的满足条件的区间个数。然后我们就可以对询问做离线，开一个 vector 来存每个左端点为 l 时每个询问 r 的值和询问的编号，由后向前枚举询问的左端点 l，每次从 a_{l+1} 向 a_{l} 扩展，然后计算 a_{l} 作为区间的左端点对 f 数组产生的影响。

那么询问 [l,r] 的答案为 \sum_{i=l}^r f_i。用树状数组维护 f 数组的区间和即可，每到达一个 l 都将对应 vector 中的所有询问 r 的答案查出来并记录下来，最后在正序输出即可。

如何计算 x 作为区间的左端点带来的贡献？

因为 x 要作为左端点对答案产生贡献，那么右端点只能是 2\times x,3\times x\dots k\times x 这些数中小于等于 n 并且位于 x 所在位置的右边的数。

此时贡献又分两种，一种是当 x\mid y 时，x 对 f_y 直接造成的贡献，另一种是当 x\mid y 并且 y\mid z 时，x 对 f_z 间接造成的贡献。因为 z 也是 x 的倍数，所以贡献只有这两种。

对贡献的计算可以使用 dp 来解决。设 dp_i 为数值 i 要增加的贡献，初始值为 dp_x\gets 1。枚举 x 满足条件的倍数 y 和 y 满足条件的倍数 z，让 dp_z\gets dp_x+dp_y。

最后将 dp_i 对应的数值 i 的 f_i 在维护的树状数组上实现 f_i\gets f_i+dp_i 即可。不要忘了清空 dp 数组。

AC code

#include <bits/stdc++.h>
#define int long long
#define lowbit(i) i&(-i)
using namespace std;
int T,n,q,dp[1000005],ans[1000005],tmp[1000005],a[1000005];
int t[1000005];
void add(int x,int c)
{
    while (x<=n)
    {
        t[x]+=c;
        x+=lowbit(x);
    }
}
int get_sum(int x)
{
    int sum=0;
    while (x>0)
    {
        sum+=t[x];
        x-=lowbit(x);
    }
    return sum;
}
int query(int l,int r)
{
    return get_sum(r)-get_sum(l-1);
}
void work()
{
    scanf("%d%d",&n,&q);
    vector<int> r[n+1];
    vector<int> no[n+1];
    for (int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        tmp[a[i]]=i;
    }
    for (int i=1;i<=q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        r[x].push_back(y);
        no[x].push_back(i);
    }
    for (int i=n;i>=1;i--)
    {
        int x=a[i];dp[x]=1;
        for (int y=x;y<=n;y+=x)
        {
            if (tmp[y]<tmp[x]) continue;
            for (int z=y*2;z<=n;z+=y)
            {
                if (tmp[z]<tmp[y]) continue;
                dp[z]+=dp[y];
            }
        }
        for (int j=x;j<=n;j+=x)
        {
            add(tmp[j],dp[j]);
            dp[j]=0;
        }
        for (int j=0;j<r[i].size();j++)
        {
            ans[no[i][j]]+=query(i,r[i][j]);
        }
    }
    for (int i=1;i<=q;i++)
    {
        cout<<ans[i]<<" ";
    }
    cout<<"\n";
    for (int i=1;i<=q;i++)
    {
        ans[i]=0;
    }
    for (int i=1;i<=n;i++)
    {
        t[i]=0;
    }
}
signed main()
{
    cin>>T;
    while (T--)
    {
        work();
    }
    return 0;
}