题目描述

麦克雷有一个1~n的排列，他想知道对于一些区间，有多少对区间内的数（x，y），满足x能被y整除。

输入

第一行包含2个正整数n，m。表示有n个数，m个询问。

接下来一行包含n个正整数，表示麦克雷有的数列。

接下来m行每行包含2个正整数l，r。表示询问区间[l,r]。

输出

共 m 行，每行一个整数，表示满足条件的对数。

样例输入

10 9

1 2 3 4 5 6 7 8 9 10

1 10

2 9

3 8

4 7

5 6

2 2

9 10

5 10

4 10

样例输出

27

14

8

4

2

1

2

7

9

数据范围

30%：1<=n,m<=100

100%：1<=n,m<=2*10^5,1<=pi<=n

解法

对于一个区间[l,r]，它的答案=区间[1,r]中的总贡献-区间[1,r]中[1,l-1]的贡献。

证明：

显然，区间[l,r]的答案=区间[1,r]的答案-区间[1,l]的答案-所有(a[i],a[j])的贡献。（其中i∈[1,l]，j∈[1,r]）

而又，区间[1,l]的答案+所有(a[i],a[j])的贡献=区间[1,r]中[1,l-1]的贡献；

所以区间[l,r]的答案=区间[1,r]中的总贡献-区间[1,r]中[1,l-1]的贡献。

如果把区间按右端点升序排序，那么使用扫描线即可将问题转化为：

区间[1,r]中，任意区间贡献和。

用树状数组维护即可。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) ll(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="aP3.in";

const char* fout="aP3.out";

const ll inf=0x7fffffff;

const ll maxn=200007,maxt=maxn*5;

ll n,m,i,j,k,l,r,ks,cnt;

ll tmp=0;

ll a[maxn],b[maxn],c[maxn];

ll ans[maxn];

ll hh[maxn];

bool bz[maxn];

struct q{

    ll l,r,id;

}qu[maxn];

bool cmp(q a,q b){

    return a.r<b.r;

}

void change(ll v,ll v1){

    if (!bz[v]) return;

    v=b[v];

    cnt+=v1;

    for (;v<=n;v+=v&-v) c[v]+=v1;

}

ll getsum(ll v){

    ll x=0;

    for (;v;v-=v&-v) x+=c[v];

    return x;

}

ll getsum(ll l,ll r){

    return getsum(r)-getsum(l-1);

}

void join(ll v){

    ll i,j,k;

    bz[a[v]]=true;

    for (i=1;i<=(ll)(sqrt(a[v]));i++){

        if (a[v]%i==0){

            change(a[v]/i,1);

            if (i*i!=a[v]) change(i,1);

        }

    }

    for (i=a[v]*2;i<=n;i+=a[v]) change(i,1);

}

int main(){

    scanf("%d%d",&n,&m);

    ks=sqrt(n);

    for (i=1;i<=n;i++){

        scanf("%d",&a[i]);

        b[a[i]]=i;

    }

    for (i=1;i<=m;i++){

        scanf("%d%d",&qu[i].l,&qu[i].r);

        qu[i].id=i;

    }

    sort(qu+1,qu+m+1,cmp);

    r=0;

    for (i=1;i<=m;i++){

        while (r<qu[i].r) {

            join(++r);

        }

        ans[qu[i].id]=cnt-getsum(qu[i].l-1);

    }

    for (i=1;i<=m;i++) printf("%lld\n",ans[i]);

    return 0;

}

启发

离线的区间问题归结为：

莫队算法

范围

对于已知区间，给其加入元素或删除元素以较低复杂度完成。

则适用莫队算法。

扩展

如果加入元素简单，删除元素难，那么就可以使用只增莫队算法。

参考这一题。

分块

坑待填

区间拆分扫描线

范围

当[1,i]容易计算时，且区间[l,r]可拆分成[1,r]和[1,l-1]；

则适用区间拆分扫描线。

参考这一题。

扩展

如果[l,r]拆分后满足ans([l,r])=ans([1,r])-ans([1,l-1])-ans(分属于[1,l-1],[l,r])；

那么是可以将ans([l,r])=ans([1,r])-[1,r]下[1,l-1]的贡献。

参考本题。