频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 4777 Rabbit Kingdom (离线树状数组)
2014-09-07 10:59:35         来源:Jinx Jinx again  
收藏   我要投稿

题目大意:

给出m个查询,查询出[ l - r] 之间去 这个区间所有的数都互质的数有多少个。


思路分析:

首先我们处理出来每一个位置,左边和右边第一个与之不互质的数的位置。记在pre 和 next下。这个方法用分解质因数就好。

一个区间内的答案,等于这个区间的所有数减去有与之互质数的个数。

现在要统计的就是

1.对于一个给定的查询[l,r] 区间,统计有多少个 i (l<= i <=r) 的pre[i] 或 next[i]在[l,r]内。

2.对于一个给定的查询[l,r]区间,统计有多个个i (l<= i < = r)的pre[i] 且 next[i] 在[l,r]内。

那么区间的答案就是 r-l+1-(统计出来的1的答案)+(统计出来的2的答案)。

对于统计2,我们就是判断有多个[pre[i],next[i] ] 在 [l,r]内。

对于统计1,我们可以用判断 [pre[i],i] 或 [i,next[i]]来替换。


#include 
#include
#include
#include
#include
#include
#define lowbit(x) (x&(-x))
#define maxn 200005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e

using namespace std;
bool vis[200005];
int prime[50000],top_prime;

int n,m;
struct foo
{
    int s,e;
    int index,ans;
    foo(){}
    foo(int st,int ed,int id):s(st),e(ed),index(id){}
    bool operator < (const foo &cmp)const
    {
        return e=1;x-=lowbit(x))ans+=bit[x];
    for(int x=l-1;x>=1;x-=lowbit(x))ans-=bit[x];
    return ans;
}
void sieve(int n)
{
    int m=(int)sqrt(n+0.5);
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=m;i++)
    {
        if(!vis[i])
        {
            for(int j=i*i;j<=n;j+=i)
                vis[j]=1;
        }
    }
    for(int i=2;i<=m;i++)
    {
        if(vis[i]==0) prime[top_prime++]=i;
    }
}
int pre[200005],next[200005],now[200005],a[200005],tnext[200005];
vector p[200005];


vector  ret[3];
int ans[3][maxn];
void getans(int key)
{
    memset(bit,0,sizeof bit);

    int ind=0;
    for(int i=1;i<=m;i++)
    {
        while(ind1) p[a[i]].push_back(tmp);
        }
        memset(now,0,sizeof(now));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j

点击复制链接 与好友分享!回本站首页
相关TAG标签 数组
上一篇:C++ vector用法的详解
下一篇:HDOJ 4430 Yukari's Birthday
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站