HDU 4777 Rabbit Kingdom(2013 항주 지구 1008 문제,예 처리,나무 모양 배열)

Rabbit Kingdom
Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 40    Accepted Submission(s): 20
Problem Description
　　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.
 
 
Input
　　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 W
i 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, W
i <= 200000, 1 <= L <= R <= n)
　　The input ends with n = 0 and m = 0.
 
 
Output
　　For every query, output one line indicating the answer.
 
 
Sample Input
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
 
 
Sample Output
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] .
 
 
Source
2013 Asia Hangzhou Regional Contest
 
 
 
관건 은 예 처리 에서 각 수가 L,R 구간 을 예 처리 해 좌우 와 이 수의 서로 질 이 맞지 않 는 위 치 를 나타 내 는 것 이다.
 
이것 은 왼쪽 에서 오른쪽으로,오른쪽 에서 왼쪽으로 한 번 스 캔 하면 질 적 요 소 를 분해 하고 다음 질 적 요소 의 위 치 를 찾 을 수 있다.
 
그리고 모든 조회 에 대해 오프라인 처 리 를 하고 오른쪽 점 에 따라 정렬 합 니 다.
 
i 를 만나면 L 에서+1,R 을 만나면 i 에서+1,L 에서-1.
 

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013-11-9 14:38:41
  4 File Name     :E:\2013ACM\      \   \2013  \1008.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 
 21 const int MAXN = 200010;
 22 int prime[MAXN+1];
 23 void getPrime()
 24 {
 25     memset(prime,0,sizeof(prime));
 26     for(int i = 2;i <= MAXN;i++)
 27     {
 28         if(!prime[i])prime[++prime[0]] = i;
 29         for(int j = 1;j <= prime[0] && prime[j] <= MAXN/i;j++)
 30         {
 31             prime[prime[j]*i] = 1;
 32             if(i % prime[j] == 0)break;
 33         }
 34     }
 35 }
 36 long long factor[100][2];
 37 int fatCnt;
 38 int getFactors(long long x)
 39 {
 40     fatCnt = 0;
 41     long long tmp = x;
 42     for(int i = 1;prime[i] <= tmp/prime[i];i++)
 43     {
 44         factor[fatCnt][1] = 0;
 45         if(tmp % prime[i] == 0)
 46         {
 47             factor[fatCnt][0] = prime[i];
 48             while(tmp % prime[i] == 0)
 49             {
 50                 factor[fatCnt][1]++;
 51                 tmp /= prime[i];
 52             }
 53             fatCnt++;
 54         }
 55     }
 56     if(tmp != 1)
 57     {
 58         factor[fatCnt][0] = tmp;
 59         factor[fatCnt++][1] = 1;
 60     }
 61     return fatCnt;
 62 }
 63 int L[MAXN],R[MAXN];
 64 int a[MAXN];
 65 int b[MAXN];
 66 int n,m;
 67 int lowbit(int x)
 68 {
 69     return x & (-x);
 70 }
 71 int c[MAXN];
 72 void add(int i,int val)
 73 {
 74     if(i == 0)return;
 75     while(i <= n)
 76     {
 77         c[i] += val;
 78         i += lowbit(i);
 79     }
 80 }
 81 int sum(int i)
 82 {
 83     int s = 0;
 84     while(i > 0)
 85     {
 86         s += c[i];
 87         i -= lowbit(i);
 88     }
 89     return s;
 90 }
 91 vector<int>vec[MAXN];
 92 struct Node
 93 {
 94     int l,r;
 95     int index;
 96     void input()
 97     {
 98         scanf("%d%d",&l,&r);
 99     }
100 };
101 bool cmp(Node p1,Node p2)
102 {
103     return p1.r < p2.r;
104 }
105 Node node[MAXN];
106 int ans[MAXN];
107 int pp[MAXN][15];
108 int main()
109 {
110     //freopen("in.txt","r",stdin);
111     //freopen("out.txt","w",stdout);
112     getPrime();
113     while(scanf("%d%d",&n,&m) == 2)
114     {
115         if(n == 0 && m == 0)break;
116         for(int i = 1;i <= n;i++)
117             scanf("%d",&a[i]);
118         for(int i = 0;i < m;i++)
119         {
120             node[i].input();
121             node[i].index = i;
122         }
123         for(int i = 1;i < MAXN;i++)b[i] = n+1;
124         for(int i = n;i >= 1;i--)
125         {
126             getFactors(a[i]);
127             R[i] = n+1;
128             pp[i][0] = fatCnt;
129             for(int j = 0;j < fatCnt;j++)
130             {
131                 R[i] = min(R[i],b[factor[j][0]]);
132                 b[factor[j][0]] = i;
133                 pp[i][j+1] = factor[j][0];
134             }
135         }
136         for(int i = 1;i < MAXN;i++)b[i] = 0;
137         for(int i = 1;i <= n;i++)
138         {
139             //getFactors(a[i]);
140             L[i] = 0;
141             fatCnt = pp[i][0];
142             for(int j = 0;j < fatCnt;j++)
143             {
144                 factor[j][0] = pp[i][j+1];
145                 L[i] = max(L[i],b[factor[j][0]]);
146                 b[factor[j][0]] = i;
147             }
148         }
149         sort(node,node+m,cmp);
150         memset(c,0,sizeof(c));
151         for(int i = 1; i <= n+1;i++)
152         {
153             c[i] = 0;
154             vec[i].clear();
155         }
156         for(int i = 1;i <= n;i++)vec[R[i]].push_back(i);
157         int id = 1;
158         for(int i = 0;i < m;i++)
159         {
160             while(id <= n && id <= node[i].r)
161             {
162                 add(L[id],1);
163                 int sz = vec[id].size();
164                 for(int j = 0;j < sz;j++)
165                 {
166                     int v = vec[id][j];
167                     add(L[v],-1);
168                     add(v,1);
169                 }
170                 id++;
171             }
172             ans[node[i].index] = sum(node[i].r) - sum(node[i].l-1);
173             ans[node[i].index] = node[i].r - node[i].l +1 - ans[node[i].index];
174         }
175         for(int i = 0;i < m;i++)printf("%d
",ans[i]);
176 
177 
178     }
179     return 0;
180 }