Rabbit Kingdom

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 964    Accepted Submission(s): 315

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的数列(1 <= n<= 200000,)数列中值的范围同n。现在有m组询问。每组询问问这个区间内的数有多少个数是与这个区间的其他数都是互质的。

思路：

开始读错题意了。居然用划分树写了。真是脑洞开得太大了。。

很容易想到的是处理每个数左边与之最近且和它不互质数的位置le[i]和右边与之最近且和它不互质数的位置ri[i].

但是答案要怎么求呢。

考虑每个数。他只有在[le[i]+1,ri[i]-1]这个区间内是有效的。所以我们离线处理询问。先对所有询问按L排序。

假设我们现在询问已经计算玩以left为左端点的询问了。现在要计算左端点为left+1的询问。由于现在计算left+1，所以

le[i]为left的点。都可能会有效了。le[i]在left右边的都是无效的。因为不管r为多少只要包含了i就一定会包含le[i]。所以i这个点都是无效的。所以我们把所有le[i]为left的点(这个可以用个邻接表维护)i的位置i加1.把位置ri[i]减1.由于left这个点以前在自己的ri[left]减了个1.现在要给它加回来。然后就能保证。询问[L,R]之间的数加起来就为满足条件数的个数了。

对于[L,R]之间的数加起来可以用树状数组维护。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=200010;
typedef long long ll;
int arr[maxn],C[maxn],ans[maxn];
bool vis[maxn+10];
int pri[maxn],prinum;
int h[maxn],le[maxn],ri[maxn];
int n,m,cnt;
struct qnode
{
    int l,r,id;
} qu[maxn];
bool cmp(qnode a,qnode b)
{
    return a.l<b.l;
}
struct node
{
    int v;
    node *next;
} eg[maxn],*head[maxn];
void adde(int u,int v)
{
    eg[cnt].v=v;
    eg[cnt].next=head[u];
    head[u]=&eg[cnt++];
}
void build_prime()
{
    int m=sqrt(maxn*1.0),i,j;
    for(i=2;i<=m;i++)
        if(!vis[i])
        {
            for(j=i*i;j<=maxn;j+=i)
                vis[j]=1;
        }
    prinum=0;
    for (i=2;i<=maxn;i++)
        if(!vis[i])
            pri[prinum++]=i;
}
void build_le(int n)
{
    memset(h,-1,sizeof h);
    for (int i=1;i<=n;i++)
    {
        int st=arr[i];
        for (int j=0;pri[j]*pri[j]<=st;j++)
            if (st%pri[j]==0)
            {
                if (h[pri[j]]!=-1) le[i]=max(le[i],h[pri[j]]);
                h[pri[j]]=i;
                while (st%pri[j]==0) st/=pri[j];
            }
        if (st!=1)
        {
            if (h[st]!=-1) le[i]=max(le[i],h[st]);
            h[st]=i;
        }
    }
}
void build_ri(int n)
{
    memset(h,-1,sizeof h);
    for (int i=n;i>=1;i--)
    {
        int st=arr[i];
        for (int j=0;pri[j]*pri[j]<=st;j++)
            if (st%pri[j]==0)
            {
                if (h[pri[j]]!=-1) ri[i]=min(ri[i],h[pri[j]]);
                h[pri[j]]=i;
                while (st%pri[j]==0) st/=pri[j];
            }
        if (st!=1)
        {
            if (h[st]!=-1) ri[i]=min(ri[i],h[st]);
            h[st]=i;
        }
    }
}
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int d)
{
    for(int i=x;i<=n;i+=lowbit(i))
        C[i]+=d;
}
int getsum(int x)
{
    int s=0;
    for(int i=x;i>0;i-=lowbit(i))
        s+=C[i];
    return s;
}
int main()
{
    int i,l,r,ct;
    build_prime();

    while(scanf("%d%d",&n,&m),n||m)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&arr[i]);
        for(i=0;i<=n;i++)
        {
            head[i]=NULL;
            C[i]=le[i]=0;
            ri[i]=INF;
        }
        build_le(n);
        build_ri(n);
        cnt=0;
        for(i=1;i<=n;i++)
            adde(le[i],i);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&l,&r);
            qu[i].l=l,qu[i].r=r;
            qu[i].id=i;
        }
        sort(qu,qu+m,cmp);
        qu[m].l=INF;
        ct=0;
        for(i=0;i<=n;i++)
        {
            while(qu[ct].l==i)
            {
                ans[qu[ct].id]=getsum(qu[ct].r)-getsum(qu[ct].l-1);
                ct++;
            }
            for(node *p=head[i];p!=NULL;p=p->next)
            {
                add(p->v,1);
                if(ri[p->v]!=INF)
                    add(ri[p->v],-1);
            }
            if(ri[i]!=INF)
                add(ri[i],1);
        }
        for(i=0;i<m;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}