2019徐州网络赛 - query

题目链接：query

题目大意：就是有m次询问，每次问一个区间当中满足 gcd(i,j) = min(i,j) 的有多少对。

当时比赛的时候，一直给我感觉就是莫队，但是一直没有维护出来。

其实满足这个条件，就是相当于 i , j 有一个倍数关系。而且又是一个全排列，所以满足这个关系的并不多，最多 n log(n) 个，于是我们就可以把所有这样的关系都预处理出来。

我们对询问按照 r 排序，然后我们每次就可以保证，当前的右区间不用维护了，然后我们就是查询所有左区间满足大于当前的询问的左区间的个数一共有多少对,每次都把当前的右区间对应满足条件的左区间，插入到树状数组里面。

这个用树状数组维护一下前缀就好了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
//#define int long long
using namespace std;
const int N=1e5+10;
int a[N],pos[N],n,m,s[N],res[N];
vector<int> v[N];
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return s1.r<s2.r;
}
inline void add(int x){
	for(int i=x;i<=n;i+=lowbit(i))	s[i]+=1;
}
inline int ask(int x){
	int res=0;	for(int i=x;i>=1;i-=lowbit(i))	res+=s[i];	return res;
}
signed main(){
	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<=n;i++)
		for(int j=i+i;j<=n;j+=i)
			v[max(pos[i],pos[j])].push_back(min(pos[i],pos[j]));
	for(int i=1;i<=m;i++)	scanf("%d %d",&t[i].l,&t[i].r),t[i].id=i;
	sort(t+1,t+1+m,cmp);	int st=1;
	for(int i=1;i<=m;i++){
		while(st<=t[i].r){
			for(int j=0;j<v[st].size();j++)	add(v[st][j]);	st++;
		}
		res[t[i].id]=ask(t[i].r)-ask(t[i].l-1);
	}
	for(int i=1;i<=m;i++)	printf("%d\n",res[i]);
	return 0;
}