传送门

题意是给一个长度为n的排列。给出m个询问，每次询问一个区间。

问区间内所有数一个数是另一个数的倍数的对数。

l \le i < j \le r 而且 \min(p_i,p_j) = \gcd(p_i,p_j )

由于是排列，n<=1e5，所以用pos[i]存下i这个数的为位置。

在nlogn的时间里可以找出所有pair的对数，并以(l,r)的二元组表示。

再把询问L,R以二元组的形式离线。

问题转化成了二维偏序问题：L \le l \ \text{and}\ r \le R

用树状数组即可解决

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
typedef pair<int,int> pii;
int pos[maxn], a[maxn];
vector<pii> v;
vector<pair<pii,int> > q;
int c[maxn];
int n, m;
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] ++ ;
}
int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
int ans[maxn];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]] = i;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j += i)
        {
            if(pos[i] < pos[j]) v.push_back({-pos[i], pos[j]});
            else if(pos[i] > pos[j]) v.push_back({-pos[j],pos[i]});
        }
    }

    for(int i = 1; i <= m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q.push_back({{-l, r}, i});
    }
    sort(q.begin(), q.end());
    sort(v.begin(), v.end());
    int i = 0, j = 0;
    for(i = 0; i < q.size(); i++)
    {
        int L = -q[i].first.first, R = q[i].first.second;
        while(j < v.size() && -v[j].first >= L) 
            add(v[j].second), j++;
        ans[q[i].second] = ask(R);
    }
    for(i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
/*
4 4
3 1 4 2
1 2
2 3
1 3
3 4
*/