query（2019徐州网络赛）（一点思维+树状数组）

query

这题和HH的项链简直是异曲同工之妙，只不过预处理不同，此题略巧妙些

题意：给定一个 $1$1~ $n$n的全排列，然后有 $m$m个询问，每次询问求 $[l,r]$[l,r]内满足条件的 $pair$pair有多少对。条件为： $pair(a,b)$pair(a,b)满足一个数是另外一个数的倍数即可

思路：

1. 记录好每个数字的位置
2. 预处理出每个数对哪些数字有贡献，并将所有有贡献的 $pair$pair保存在靠右的位置（略显巧妙，见代码，这个方法复杂度为调和级数的复杂度， $O\left(nlogn\right)$O(nlogn)）
3. 将所有询问也记录在右端点上
4. 最后从最左边到最右边扫一遍，在每个位置现将当前位置的有贡献的左端点插入到树状数组中，然后处理右端点在当前位置的询问；并且处理好以后树状数组不用清空（自行体会）

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-7;

struct P{
    int l, id;
};
vector<int> l[maxn];
vector<P> q[maxn];
int n, m, a[maxn], b[maxn], pos[maxn], ans[maxn];

inline void add(int x, int d) { while(x<=n) b[x]+=d, x+=x&-x; }
inline int sum(int x) { int ans=0; while(x) ans+=b[x], x-=x&-x; return ans; }

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read();
    for(int i=1; i<=n; ++i) pos[a[i]=read()]=i;
    for(int i=1; i<=n; ++i)
        for(int j=a[i]*2; j<=n; j+=a[i]) l[max(i,pos[j])].push_back(min(i,pos[j]));
    for(int i=1; i<=m; ++i) {
        int l=read(), r=read();
        q[r].push_back((P){l,i});
    }
    for(int i=1; i<=n; ++i) {
        for(auto p: l[i]) add(p,1);
        for(auto p: q[i]) ans[p.id]=sum(i)-sum(p.l-1);
    }
    for(int i=1; i<=m; ++i) printf("%d\n", ans[i]);
}