*query【思维+树状数组】

题意：

给定一个 \(1\to n\) 的全排列，有 \(m\) 个询问，每次询问求 \([l,r]\) 内有多少满足 \(l\le i<j\le r,min(p_i,p_j) = gcd(p_i,p_j)\) 的 \(pair(i,j)\)。
题目链接：https://nanti.jisuanke.com/t/41391

分析：

  这题的难点主要是思维的转化。联想用树状数组处理逆序对问题，大体思路和本题差不多。也是在权值上计数，然后按照某一种特定的顺序来放数。
大体过程：
  先处理出有倍数关系的位置，求出对于一个靠后的位置，有哪些靠前的位置对它有贡献。把查询保存下来，进行离线处理。从前到后遍历位置，对于当前位置 \(i\) ，把对它有贡献的位置的值加上，然后处理掉以该点为右端点区间查询。

代码：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+5;
int a[N],pos[N],bit[N],n,ans[N];
vector<pii>q[N];
vector<int>num[N];
void add(int x)
{
    while(x<=n)
    {
        bit[x]++;
        x+=(x&(-x));
    }
}
int query(int x)
{
    int res=0;
    while(x>0)
    {
        res+=bit[x];
        x-=(x&(-x));
    }
    return res;
}
int main()
{
    int m,l,r;
    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<=m;i++)
    {
        scanf("%d%d",&l,&r);
        q[r].pb(make_pair(l,i));
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=a[i]*2;j<=n;j+=a[i])
            num[max(i,pos[j])].pb(min(i,pos[j]));//哪些小位置对哪些大位置有贡献
    }
    for(int i=1;i<=n;i++)//按位置遍历
    {
        for(int j=0;j<num[i].size();j++)
            add(num[i][j]);
        for(int j=0;j<q[i].size();j++)
            ans[q[i][j].second]=query(i)-query(q[i][j].first-1);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}