题目链接：codeforces 301D
题意分析： 给你n , m两个数，1≤n,m≤2e5，n代表n个不同数字，且这些数字都在区间[ 1 , n ]之间，这就说明1~n每个数出现一次。m代表m次查询，查询格式为两个整数x , y，问你区间[ x , y ]之间有多少对数a , b满足a%b==0。
解题思路： 考察点是区间的频繁访问，马上想到线段树和树状数组，线段树太难写了没考虑过，就说说树状数组的思路吧。 1）离线处理：把所有的插叙全部读进来再按特定顺序处理。为了让树状数组求的和确确实实的是属于这个区间的，没有别的区间的干扰，我们按区间的左边界给区间排一次序，左边界大的先处理：
bool cmp(query a,query b){return a.x>b.x;}
2）预处理：找到跟ai的所有可整除的数，根据索引大小保存在一个vector里面：
for(int i=1;i<=n;i++){for(int j=a[i];j<=n;j+=a[i]){if(p[j]>=i)vec[i].push_back(p[j]);elsevec[p[j]].push_back(i);}}
3）树状数组处理：有一个虚拟数组cnt 首先有一个maxx变量，来记录当前已经处理到哪了（从右到左处理，初始值为n+1），来达到避免重复计算的效果。把所有该加上的值先加上，在求和；如果之前已经加过了，不用加了，，这里就需要maxx来判断了：
int maxx=n+1;for(int i=0;i<m;i++){int x=q[i].x,y=q[i].y,len;for(int j=x;j<maxx;j++){len=vec[j].size();for(int k=0;k<len;k++)add(vec[j][k],1);}ans[q[i].id]=sum(y); //求和maxx=x;}
AC代码：
using namespace std;int n,m,a[200005],p[200005],bit[200005],ans[200005];vector<int> vec[200005];struct query{int id,x,y;}q[200005];bool cmp(query a,query b){return a.x>b.x;}int lowbit(int num){return num&(-num);}int sum(int index){int res=0;for(int i=index;i>0;i-=lowbit(i))res+=bit[i];return res;}void add(int index,int delta){for(int i=index;i<=n;i+=lowbit(i))bit[i]+=delta;}int main(){scanf(“%d %d”,&n,&m);for(int i=1;i<=n;i++){scanf(“%d”,&a[i]);p[a[i]]=i;}for(int i=1;i<=n;i++){for(int j=a[i];j<=n;j+=a[i]){if(p[j]>=i)vec[i].push_back(p[j]);elsevec[p[j]].push_back(i);}}for(int i=0;i<m;i++){scanf(“%d %d”,&q[i].x,&q[i].y);if(q[i].y<q[i].x)swap(q[i].x,q[i].y);q[i].id=i;}sort(q,q+m,cmp);int maxx=n+1;for(int i=0;i<m;i++){int x=q[i].x,y=q[i].y,len;for(int j=x;j<maxx;j++){len=vec[j].size();for(int k=0;k<len;k++)add(vec[j][k],1);}ans[q[i].id]=sum(y);maxx=x;}for(int i=0;i<m;i++)printf(“%d\n”,ans[i]);return 0;}
总结： 1、离线处理+树状数组 2、注意查询的排序方式
走一个地方停一个地方。在我心里最美好的就是和你一起老在路上，
