首页 > 代码库 > 13杭州区域赛现场赛Rabbit Kingdom（树状数组+离线）

13杭州区域赛现场赛Rabbit Kingdom（树状数组+离线）

2024-07-03 23:52:42   222人阅读

题意：给你一个长度数列，再给你m个询问（一个区间），问你在这个区间里面有多少个数与其他的数都互质。

解题思路：你看这种类型的题目都可以肯定这是 离线+树状数组（线段树）。主要就是他的更新信息。这里我的处理是先把1-200000（每个数的范围）数里面所有的质因子求出来。然后从后往前遍历数组。会出现以下几种情况

          1.a[k]的质因子在后面出现过而【更新标记】 和【被更新标记】 都为假

          2.a[k]的质因子在后面出现过的那个位置 I   【更新标记】为 真 。

          3.a[k]的质因子在后面出现过且那个位置 I  【被更新标记】  为真 。

    如果只出现 1 这种情况，那么这个位置   +1，【更新标记】 变为真；

    如果只出现 2 这种情况， 那么对这个位置不更新。

    如果出现 3 这种情况， 那么  I  的被更新位置 -1  ，I位置 +1  ，且 I的被更新标记变为假。

    在这个过程中，a[k]的所有质因子的 最新位置 都变为K ，再找到到离 a【K】 最近的和它 不互质的数 a【X】 把K的 【被更新标记】变为  X，再在X位置 +1

    （上面所有的操作都是为了使得记数不 错误）

      最后的答案就是   区间内数的个数 - 区间求的和。

解题代码：

  1 // File Name: c.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年05月07日 星期三 17时07分23秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 
 25 using namespace std;
 26 #define MAXN  200005
 27 
 28 
 29 int a[MAXN];
 30 struct lr{
 31     int l,r,num;
 32 }q[MAXN];
 33 int cmp(lr a, lr b)
 34 {
 35     return a.l > b.l;
 36 }
 37 int tree[MAXN];
 38 int lowbit(int x)
 39 {
 40     return x&(-x);
 41 }
 42 int getsum(int l,int k)
 43 {
 44     int sum = 0 ; 
 45     while(k >= l )
 46     {
 47         sum += tree[k];
 48         k -= lowbit(k);
 49     }
 50     return sum ; 
 51 }
 52 int n;
 53 int hs[MAXN];
 54 void update(int k  ,int v )
 55 {
 56     //    printf("%d\n",k);
 57     while(k <= n)
 58     {
 59         tree[k] += v; 
 60         k += lowbit(k);
 61     }
 62 
 63 }
 64 int ans[MAXN];
 65 int prime[MAXN][20];
 66 int num[MAXN];
 67 int last[MAXN];
 68 void solve(){
 69     memset(num,0,sizeof(num));
 70     memset(hs,0,sizeof(hs));
 71     for(int i = 2 ;i <= 200000;i ++)
 72     {
 73         if(hs[i] == 0 )
 74         {
 75             int k = i;
 76             while(k <= 200000)
 77             {
 78                 num[k] ++ ; 
 79                 prime[k][num[k]] = i ; 
 80                 hs[k] = 1; 
 81                 k += i ;
 82             }
 83         }
 84     }
 85 }
 86 int isupdate[MAXN];
 87 int cmp1(int a, int b)
 88 {
 89     return a < b ;
 90 }
 91 int main(){
 92     //freopen("intpu.in","r",stdin);
 93     int m ;
 94     solve();
 95     //printf("***\n");
 96     while(scanf("%d %d", &n,&m) != EOF)
 97     {
 98         if(n == 0 && m == 0 )
 99             break;
100         memset(tree,0,sizeof(tree));
101         memset(q,0,sizeof(q));
102         
103         
104         for(int i = 1;i <= n;i ++)
105             scanf("%d",&a[i]);
106         for(int i = 1;i <= m;i ++)
107         {
108             scanf("%d %d",&q[i].l,&q[i].r);
109             q[i].num = i; 
110         }
111         sort(q+1,q+m+1,cmp);
112         
113         int p = 1;
114         memset(hs,0,sizeof(hs));
115         memset(last,0,sizeof(last));
116         memset(isupdate,0,sizeof(isupdate));
117         //memset(q,0,sizeof(q));
118         for(int i = n;i >= 1 ;--i)
119         {
120             int ta[20];
121             int tanum = 0 ; 
122             memset(ta,0,sizeof(ta));
123             for(int j = 1; j <= num[a[i]]; ++j )
124             {
125                 int temp = prime[a[i]][j];
126                 if(hs[temp])
127                 {
128                     tanum ++ ; 
129                     ta[tanum] = hs[temp];
130                 }
131                 hs[temp] = i ; 
132             }
133             if(tanum)
134             {
135                 sort(ta+1,ta+tanum+1,cmp1);
136                 int min = ta[1];
137                 for(int j = 1;j <= tanum;j ++)
138                 {
139                     if(ta[j]!= ta[j-1])
140                     {
141                         if(last[ta[j]])
142                         {
143                             update(last[ta[j]],-1);
144                             update(ta[j],1);
145                             last[ta[j]] = 0 ; 
146                            }else {
147                               if(!isupdate[ta[j]])
148                               {
149                                  update(ta[j],1);
150                                  isupdate[ta[j]] = 1 ; 
151                               }
152                         }
153                        if(ta[j] < min)
154                           min = ta[j];
155                     }
156                 }
157                 update(min,1);
158                 isupdate[min] = 1; 
159                 last[i] = min;
160                 isupdate[i] = 1;
161 
162             }
163             while(q[p].l == i )
164             {
165                 ans[q[p].num] = (q[p].r - q[p].l +1) - getsum(q[p].l,q[p].r);
166                 p++;
167             }
168         }
169         for(int i = 1;i <= m;++i)
170             printf("%d\n",ans[i]);
171     }
172     return 0;
173 }
很难

 

 


联系
我们