程序员人生网站导航

CodeForces 301D（树状数组）

栏目：php教程时间：2015-06-27 08:32:37

题目链接：codeforces 301D

题意分析：
给你n , m两个数，1?≤?n,?m?≤?2e5，n代表n个不同数字，且这些数字都在区间[ 1 , n ]之间，这就说明1~n每一个数出现1次。m代表m次查询，查询格式为两个整数x , y，问你区间[ x , y ]之间有多少对数a , b满足a%b==0。

解题思路：
考察点是区间的频繁访问，马上想到线段树和树状数组，线段树太难写了没斟酌过，就说说树状数组的思路吧。
1）离线处理：把所有的插叙全部读进来再按特定顺序处理。为了让树状数组求的和确确切实的是属于这个区间的，没有别的区间的干扰，我们按区间的左侧界给区间排1次序，左侧界大的先处理：

bool cmp(query a,query b){
    return a.x>b.x;
}

2）预处理：找到跟ai的所有可整除的数，根据索引大小保存在1个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]);
        else
            vec[p[j]].push_back(i);
    }
}

3）树状数组处理：有1个虚拟数组cnt
首先有1个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代码：

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

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]);
            else
                vec[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
",ans[i]);

    return 0;
}

总结：
1、离线处理+树状数组
2、注意查询的排序方式

------分隔线----------------------------

上一篇 linux应用开发-进程控制理论

下一篇 单元测试之如何测试模板类

------分隔线----------------------------