【树状数组】2019徐州网络赛 query

（2）首先成倍数对的数量是nlogn级别的，考虑每一对【xL，xR】(下标的位置，xL < xR)会对那些询问做出贡献，如果qL <= xL && qR >= xR，那么这一对就会对询问【qL，qR】贡献1；现在把它们看成平面上的点，那么对于每一个询问【qL，qR】，就相当于计算这个点右下角有多少个点，这个就可以通过排序+树状数组解决
————————————————
大致就是，我们可以先处理出区间内每一对（i，j）倍数对，然后按i从大到小排序
排序介绍：按i排序，从大到小，再让添加在前，询问在后，例如，我们区间（1，2，4，6）
然后倍数对就有（1 2，1 3 ，1 4，2 4）我们让2 4排前边，这样就可以一个个当成点来使用树状数组，这样保证先询问到就是刚加进去的
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 1e5+15;
const int maxm = 2e6+26;
int n,m,a[maxn],pos[maxn];
struct node{ //f标记是倍数对还是询问，id标识询问的编号
int f,l,r,id;
}p[maxm];
bool cmp(node a,node b){
if(a.l == b.l) return a.f < b.f;
return a.l > b.l;
}
inline int lowbit(int x){
return x & (-x);
}
LL tr[maxn],ans[maxn];
void updata(int x,int val){
while(x <= n){tr[x] += val; x += lowbit(x);}
}
LL query(int x){
LL res = 0;
while(x){res += tr[x]; x -= lowbit(x);}
return res;
}
int main(){
scanf("%d %d",&n,&m); int cnt = m;
for(int i = 1;i <= n; ++i) scanf("%d",a+i),pos[a[i]] = i;
for(int i = 0;i < m; ++i) scanf("%d %d",&p[i].l,&p[i].r),p[i].f=1,p[i].id=i;
for(int i = 1;i <= n; ++i){
for(int j = a[i]*2;j <= n; j+=a[i]){
if(pos[a[i]] < pos[j]) p[cnt++] = (node){0,pos[a[i]],pos[j],0};
else p[cnt++] = (node){0,pos[j],pos[a[i]],0};
}
}
sort(p,p+cnt,cmp);
for(int i = 0;i < cnt; ++i){
if(p[i].f == 1) ans[p[i].id] = query(p[i].r);
else updata(p[i].r,1);
}
for(int i = 0;i < m; ++i) cout << ans[i] << '\n';
return 0;
}

【树状数组】2019徐州网络赛 query的相关教程结束。