首页 > ACM题库 > HDU-杭电 > HDU 4777-Rabbit Kingdom[解题报告]HOJ
2015
09-17

HDU 4777-Rabbit Kingdom[解题报告]HOJ

Rabbit Kingdom

问题描述 :

  Long long ago, there was an ancient rabbit kingdom in the forest. Every rabbit in this kingdom was not cute but totally pugnacious, so the kingdom was in chaos in season and out of season.
  n rabbits were numbered form 1 to n. All rabbits’ weight is an integer. For some unknown reason, two rabbits would fight each other if and only if their weight is NOT co-prime.
  Now the king had arranged the n rabbits in a line ordered by their numbers. The king planned to send some rabbits into prison. He wanted to know that, if he sent all rabbits between the i-th one and the j-th one(including the i-th one and the j-th one) into prison, how many rabbits in the prison would not fight with others.
  Please note that a rabbit would not fight with himself.

输入:

  The input consists of several test cases.
  The first line of each test case contains two integer n, m, indicating the number of rabbits and the queries.
  The following line contains n integers, and the i-th integer Wi indicates the weight of the i-th rabbit.
  Then m lines follow. Each line represents a query. It contains two integers L and R, meaning the king wanted to ask about the situation that if he sent all rabbits from the L-th one to the R-th one into prison.
  (1 <= n, m, Wi <= 200000, 1 <= L <= R <= n)
  The input ends with n = 0 and m = 0.

输出:

  The input consists of several test cases.
  The first line of each test case contains two integer n, m, indicating the number of rabbits and the queries.
  The following line contains n integers, and the i-th integer Wi indicates the weight of the i-th rabbit.
  Then m lines follow. Each line represents a query. It contains two integers L and R, meaning the king wanted to ask about the situation that if he sent all rabbits from the L-th one to the R-th one into prison.
  (1 <= n, m, Wi <= 200000, 1 <= L <= R <= n)
  The input ends with n = 0 and m = 0.

样例输入:

3 2
2 1 4
1 2
1 3
6 4
3 6 1 2 5 3
1 3
4 6
4 4
2 6
0 0

样例输出:

2
1
1
3
1
2
Hint
  In the second case, the answer of the 4-th query is 2, because only 1 and 5 is co-prime with other numbers in the interval [2,6] .

题意:给N个数,有M个查询,问区间[L,R]之间有多少个数与这个区间内的其他数都互质。

易得,一个区间内的数的个数减去,与其他数不互质的数即可——即离当前数i左边最近的不互质的数的位置(设为L[i])和右边最近的不互质的数的位置(设为R[i])有一个在区间[L,R]内。那么问题就变成统计:1.区间[L,R]中有多少个数的L[i]或R[i]在区间[L,R]内。2.多少个数的L[i]且R[i]在区间[L,R]内。对于每个询问,答案就是区间内的数减去1的结果,再加上2的结果。

2的结果其实就是询问有多少个区间[L[i],R[i]]完全在给定区间[L,R]内。其实1也可以转化为相同的问题,即区间[L[i],i]或[R[i],i],是否在给定区间内。

对于问有多少个区间是在给定的区间内,可以直接离线搞。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#define maxn 1000010
#define oo 1000000000
#define clearAll(a) memset(a,0,sizeof(a))
#define sq(a) ((a)*(a))

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))

using namespace std;

typedef long long ll;

const int N=200015;

struct Range
{
    int st,ed,ind;
    Range(){}
    Range(int st,int ed,int ind) :
        st(st),ed(ed),ind(ind) {}
    bool operator<(const Range &B)const
    {
        return ed<B.ed;
    }
};

int n,m,mx;
int A[N],L[N],R[N],pos[N];
int ans[3][N],num[N];

vector<Range>rab[3],range;

void fun(bool flag)
{
    if(flag==0)
    {
        for(int i=0;i<=mx;i++) pos[i]=0;

        for(int i=1;i<=n;i++)
        {
            int tmp=A[i];
            for(int j=2;j*j<=tmp;j++)
            {
                if(tmp%j) continue;
                L[i]=max(L[i],pos[j]);
                pos[j]=i;
                while(tmp%j==0) tmp/=j;
            }
            if(tmp!=1)
            {
                L[i]=max(L[i],pos[tmp]);
                pos[tmp]=i;
            }
        }
    }
    else
    {
        for(int i=0;i<=mx;i++) pos[i]=n+1;

        for(int i=n;i>=1;i--)
        {
            int tmp=A[i];
            for(int j=2;j*j<=tmp;j++)
            {
                if(tmp%j) continue;
                R[i]=min(R[i],pos[j]);
                pos[j]=i;
                while(tmp%j==0) tmp/=j;
            }
            if(tmp!=1)
            {
                R[i]=min(R[i],pos[tmp]);
                pos[tmp]=i;
            }
        }
    }
}


struct BIT
{
    int T[N];

    void clear() { for(int i=1;i<=n+10;i++) T[i]=0; }

    int lowbit(int x) { return x&(-x); }
    void updata(int pos)
    {
        if(pos==0||pos==n+1) return;
        for(int i=pos;i<=n;i+=lowbit(i)) T[i]++;
    }
    int query(int st,int ed)
    {
        int ans=0;
        for(int i=ed;i>=1;i-=lowbit(i)) ans+=T[i];
        for(int i=st-1;i>=1;i-=lowbit(i)) ans-=T[i];
        return ans;
    }
}seg;

void getAns(int key)
{
    seg.clear();

    int ind=0;
    for(int i=0;i<m;i++)
    {
        int st=range[i].st;
        int ed=range[i].ed;
        int id=range[i].ind;

        while(ind<n&&rab[key][ind].ed<=ed)
        {
            seg.updata(rab[key][ind].st);
            ind++;
        }
        ans[key][id]+=seg.query(st,ed);
    }
}

int main()
{

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;

        range.clear(); mx=0;
        rab[0].clear(); rab[1].clear(); rab[2].clear();

        for(int i=0;i<N;i++)
        {
            L[i]=0; R[i]=n+1;
            ans[0][i]=ans[1][i]=ans[2][i]=0;
        }

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&A[i]);
            mx=max(mx,A[i]);
        }
        for(int i=0;i<m;i++)
        {
            int x,y; scanf("%d%d",&x,&y);
            num[i]=y-x+1;
            range.push_back(Range(x,y,i));
        }

        fun(0); fun(1);

        for(int i=1;i<=n;i++)
        {
            rab[0].push_back(Range(L[i],i,0));
            rab[1].push_back(Range(i,R[i],0));
            rab[2].push_back(Range(L[i],R[i],0));
        }

        sort(range.begin(),range.end());
        sort(rab[0].begin(),rab[0].end());
        sort(rab[1].begin(),rab[1].end());
        sort(rab[2].begin(),rab[2].end());

        getAns(0);
        getAns(1);
        getAns(2);

        for(int i=0;i<m;i++) printf("%d\n",num[i]-ans[0][i]-ans[1][i]+ans[2][i]);
    }
    return 0;
}

参考:http://blog.csdn.net/shiqi_614/article/details/15419815