这题挺有意思哈！！！看别人写的博客，感觉瞬间就懂了。
这道题大概题意就是，给一串序列，我们要查找到l-r区间内，满足min(a[ i ],a[ j ]) = gcd(a[ i ],a[ j ])
其实我们把这个东西看成一个二元组，<i,j> 二元组满足 min(a[ i ],a[ j ]) = gcd(a[ i ],a[ j ])
为了保证唯一性，<i,j>二元组满足i<j ，min(a[ i ],a[ j ]) = gcd(a[ i ],a[ j ])
由于是排列，我们可以枚举所有的满足条件的<i,j>，并且保证二元组唯一。
这样我们就转换为一个二维偏序问题。
对于询问<l,r>我们需要回答满足条件的二元组<i,j> 满足 l<=i 且 j<=r 的二元组的组数。
那我们把询问全部离线并加入修改操作，然后排序第一维度的r，保证r的有序，对于r相同的修改和询问，先进行修改
（因为先要生成序列，询问实际上是后面进行的），维护了r后，保证了树状数组里面<i,j> j<=r，然后查询>=l的个数。
查询query(n)-query(l-1)即可，注意如果是l==1的话，避免树状数组超时直接查query(n)。就实现了二维偏序的查询。
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e6+;
struct node{
int l,r,id;
bool operator < (const node &s) const {
if (r==s.r){
return id<s.id;
}
return r<s.r;
}
}q[*maxx];
int ans[maxx];
int pos[maxx];
int tot,n;
int sum[maxx];
int lowbit(int x){
return x&(-x);
}
void add(int x,int w){
for(int i=x;i<=n;i+=lowbit(i)){
sum[i]+=w;
}
}
int query(int x){
int s=;
for (int i=x;i;i-=lowbit(i)){
s+=sum[i];
}
return s;
}
int main(){
int m;
scanf("%d%d",&n,&m);
tot=;
memset(ans,,sizeof(ans));
memset(pos,,sizeof(pos));
memset(sum,,sizeof(sum));
int tmp;
for (int i=;i<=n;i++){
scanf("%d",&tmp);
pos[tmp]=i;
}
for (int i=;i<=n;i++){
for (int j=;i*j<=n;j++){
q[++tot]=node{min(pos[i],pos[i*j]),max(pos[i],pos[i*j]),};
}
}
int l,r;
for (int i=;i<=m;i++){
scanf("%d%d",&l,&r);
q[++tot]=node{l,r,i};
}
sort(q+,q++tot);
for (int i=;i<=tot;i++){
if (q[i].id==){
add(q[i].l,);
}else {
if (q[i].l==){
ans[q[i].id]=query(n);
}else{
ans[q[i].id]=query(n)-query(q[i].l-);
}
}
}
for (int i=; i<=m; i++)
{
printf("%d\n",ans[i]);
}
return ;
}
