CF1946F Nobody is needed

思路

首先考虑只有一个询问，区间为 $[1,n]$ 的做法。

定义 $dp_i$ 表示前 $i$ 个数中，以 $a_i$ 结尾的方案数。容易得到状态转移方程：

$$dp_i = 1 + \sum_{j < i \wedge a_j \mid a_i}{dp_j}$$

最后的答案就是 $\sum_{i = 1}^n{dp_i}$。

考虑如何将这种方法推广。首先将询问离线下来，发现枚举 $r$ 不好确定 $dp$ 数组，于是考虑枚举 $l$，维护 $l + 1$ 到 $l$，$dp$ 数组的变化。

你发现，当加入一个 $a_l$ 时，会改变的 $dp$ 值的位置 $i$，一定满足 $i > l \wedge a_l \mid a_i$。于是直接枚举 $a_l$ 的倍数的位置进行转移即可。

发现最后算答案需要累一个前缀和，但是每一个 $l$ 求一个复杂度就不行了，所以需要利用树状数组优化一下。

注：本题卡常，不要全开 long long，需要的才开 long long。

Code

#include <bits/stdc++.h>
#define fst first
#define snd second
#define re register
#define ll long long

using namespace std;

typedef pair<int,int> pii;
const int N = 1e6 + 10;
int n,q;
int arr[N],p[N];
ll dp[N],ans[N];
vector<pii> Q[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

struct BIT{
    #define lowbit(x) (x & -x)

    ll tr[N];

    inline void modify(int x,ll k){
        for (re int i = x;i <= n;i += lowbit(i)) tr[i] += k;
    }

    inline ll query(int x){
        ll res = 0;
        for (re int i = x;i;i -= lowbit(i)) res += tr[i];
        return res;
    }

    #undef lowbit
}T;

inline void solve(){
    n = read(),q = read();
    fill(T.tr + 1,T.tr + n + 1,0);
    for (re int i = 1;i <= n;i++){
        p[arr[i] = read()] = i;
        Q[i].clear();
    }
    for (re int i = 1;i <= q;i++){
        int l,r; l = read(),r = read();
        Q[l].push_back({r,i});
    }
    for (re int l = n;l;l--){
        dp[l] = 1;
        for (re int x = arr[l];x <= n;x += arr[l]){
            if (p[x] < p[arr[l]]) continue;
            for (re int y = x;y <= n;y += x){
                if (p[y] <= p[x]) continue;
                dp[p[y]] += dp[p[x]];
            }
            T.modify(p[x],dp[p[x]]); dp[p[x]] = 0;
        }
        for (auto u:Q[l]) ans[u.snd] = T.query(u.fst);
    }
    for (re int i = 1;i <= q;i++) printf("%lld ",ans[i]);
    puts("");
}

signed main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}