CF301D Yaroslav and Divisors

因为是排列，所以数对总数是调和级数的 \(O(n\log n)\) 级别，可以暴力枚举。

考虑区间左右端点均在 \([l,r]\) 中的数对数量，其等于左右端点均在 \([1,r]\) 中的数对数量减去左右端点均在 \([1,l-1]\) 中的数对数量，再减去左端点在 \([1,l-1]\) 中、右端点在 \([l,r]\) 中的数对数量。

发现前两个的形式是一样的，而且很好算，只要从小到大枚举右端点然后套路地用数状数组统计左端点的贡献即可。

对于最后这个东西，我们从小到大枚举它的分界点即 \(l\)，这样左端点的限制就被搞好了，接着只需查询右端点在 \([l,r]\) 中的数对数量即可，这个同样用树状数组。

时间复杂度 \(O(n\log n)\)。

code:

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define For(i,x,y)for(i=x;i<=(y);i++)
#define lowbit(x)((x)&-(x))
struct number
{
	int l,r,id;
}p[N],q[N];
int tot[N],pos[N],c[N],a[N],n;
int read()
{
	int A;
	bool K;
	char C;
	C=A=K=0;
	while(C<‘0‘||C>‘9‘)K|=C==‘-‘,C=getchar();
	while(C>‘/‘&&C<‘:‘)A=(A<<3)+(A<<1)+(C^48),C=getchar();
	return(K?-A:A);
}
void write(int X)
{
	if(X<0)putchar(‘-‘),X=-X;
	if(X>9)write(X/10);
	putchar(X%10|48);
}
inline bool cmp1(number _,number __)
{
	return _.l<__.l;
}
inline bool cmp2(number _,number __)
{
	return _.r<__.r;
}
void add(int x)
{
	while(x<=n)c[x]++,x+=lowbit(x);
}
int sum(int x)
{
	int ret=0;
	while(x)ret+=c[x],x-=lowbit(x);
	return ret;
}
int main()
{
	int m,i,h,j,k;
	n=read(),m=read();
	For(i,1,n)a[i]=read(),pos[a[i]]=i;
	For(i,1,m)
	{
		p[i].id=q[i].id=i;
		p[i].l=read(),p[i].r=read();
		q[i].l=p[i].l,q[i].r=p[i].r;
	}
	sort(p+1,p+m+1,cmp1);
	sort(q+1,q+m+1,cmp2);
	j=k=1;
	For(i,1,n)
	{
		while(j<=m&&p[j].l==i)tot[p[j].id]-=sum(p[j].r)-sum(p[j].l-1),j++;
		h=a[i];
		while(h<=n)add(pos[h]),h+=a[i];
		while(k<=m&&q[k].r==i)tot[q[k].id]+=sum(q[k].r)-sum(q[k].l-1),k++;
	}
	For(i,1,m)write(tot[i]),putchar(‘\n‘);
	return 0;
}

CF301D Yaroslav and Divisors

原文：https://www.cnblogs.com/May-2nd/p/15032128.html