ZOJ 3911 Prime Query（线段树）

Prime Query

Time Limit: 1 Second Memory Limit: 196608 KB

You are given a simple task. Given a sequence A[i] with N numbers. You have to perform Q operations on the given sequence.

Here are the operations:

A v l, add the value v to element with index l.(1<=V<=1000)
R a l r, replace all the elements of sequence with index i(l<=i<= r) with a(1<=a<=10^6) .
Q l r, print the number of elements with index i(l<=i<=r) and A[i] is a prime number

Note that no number in sequence ever will exceed 10^7.

Input

The first line is a signer integer T which is the number of test cases.

For each test case, The first line contains two numbers N and Q (1 <= N, Q <= 100000) - the number of elements in sequence and the number of queries.

The second line contains N numbers - the elements of the sequence.

In next Q lines, each line contains an operation to be performed on the sequence.

Output

For each test case and each query,print the answer in one line.

Sample Input

Sample Output

来自 <http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3911>

【题意】：

单点修改，区间修改，查询区间素数个数

【解题思路】：

维护线段树，结点内容为：Val-实时数值(只针对单点) Sum-区间素数个数 Lazy-区间修改后传递给子区间

关键点在于数值和素数标记的同时更新和传递，由于区间更新时没有直接更新到最底层，故单点查询也需要pushdown操作。这里选择将区间更新后的值直接下传，至于素数标记，下传后再进行判断并赋值。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #define mid(a,b) ((a+b)>>1)
  7 #define LL int
  8 #define maxn 110000
  9 #define IN freopen("in.txt","r",stdin);
 10 using namespace std;
 11 
 12 char is_prime[maxn*100];
 13 void sieve()
 14 {
 15     int m=(int)sqrt((maxn*100)+0.5);
 16     fill(is_prime,is_prime+(maxn*100),1);
 17     is_prime[0]=is_prime[1]=0;
 18     for(int i=2;i<=m;i++) if(is_prime[i])
 19         for(int j=i*i;j<(maxn*100);j+=i) is_prime[j]=0;
 20 }
 21 
 22 int n,q;
 23 LL num[maxn];
 24 struct Tree
 25 {
 26     int left,right;
 27     LL sum;
 28     LL val,lazy;
 29 }tree[maxn<<2];
 30 
 31 
 32 /*递归建树*/
 33 void build(int i,int left,int right)
 34 {
 35     tree[i].left=left;
 36     tree[i].right=right;
 37     tree[i].lazy=0;
 38 
 39     if(left==right){
 40         tree[i].val=num[left];
 41         tree[i].sum=(is_prime[num[left]]? 1:0);
 42         return ;
 43     }
 44 
 45     int mid=mid(left,right);
 46 
 47     build(i<<1,left,mid);
 48     build(i<<1|1,mid+1,right);
 49 
 50     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 51 }
 52 
 53 /*区间修改，标记下传：每当访问到当前结点的子节点时，下传标记*/
 54 void pushdown(int i)
 55 {
 56     if(tree[i].lazy){
 57         int tmp = (is_prime[tree[i].lazy]? 1:0);
 58         tree[i<<1].val=tree[i].lazy;
 59         tree[i<<1|1].val=tree[i].lazy;
 60         tree[i<<1].lazy=tree[i].lazy;
 61         tree[i<<1|1].lazy=tree[i].lazy;
 62         tree[i<<1].sum=(tree[i<<1].right-tree[i<<1].left+1)*tmp;
 63         tree[i<<1|1].sum=(tree[i<<1|1].right-tree[i<<1|1].left+1)*tmp;
 64         tree[i].lazy=0; /*下传后清零*/
 65     }
 66 }
 67 
 68 /*区间修改，d为改变量*/
 69 void update(int i,int left,int right,LL d)
 70 {
 71     if(tree[i].left==left&&tree[i].right==right)
 72     {
 73         int tmp = (is_prime[d]? 1:0);
 74         tree[i].sum=(right-left+1)*tmp;
 75         tree[i].val=d;
 76         tree[i].lazy=d;
 77         return ;
 78     }
 79 
 80     pushdown(i);
 81 
 82     int mid=mid(tree[i].left,tree[i].right);
 83 
 84     if(right<=mid) update(i<<1,left,right,d);
 85     else if(left>mid) update(i<<1|1,left,right,d);
 86     else
 87     {
 88         update(i<<1,left,mid,d);
 89         update(i<<1|1,mid+1,right,d);
 90     }
 91 
 92     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
 93 }
 94 
 95 /*单点修改，d为改变量*/
 96 void update(int i,int x,LL d)
 97 {
 98     if(tree[i].left==tree[i].right){
 99         tree[i].val+=d;
100         tree[i].sum=(is_prime[tree[i].val]? 1:0);
101         return;
102     }
103 
104     pushdown(i);
105     int mid=mid(tree[i].left,tree[i].right);
106 
107     if(x<=mid) update(i<<1,x,d);
108     else update(i<<1|1,x,d);
109 
110     tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
111 }
112 
113 /*区间结果查询*/
114 LL query(int i,int left,int right)
115 {
116     if(tree[i].left==left&&tree[i].right==right)
117         return tree[i].sum;
118 
119     pushdown(i);
120 
121     int mid=mid(tree[i].left,tree[i].right);
122 
123     if(right<=mid) return query(i<<1,left,right);
124     else if(left>mid) return query(i<<1|1,left,right);
125     else return query(i<<1,left,mid)+query(i<<1|1,mid+1,right);
126 }
127 
128 
129 int main(int argc, char const *argv[])
130 {
131     //IN;
132 
133     sieve();
134     int t;scanf("%d",&t);
135     while(t--)
136     {
137         scanf("%d %d",&n,&q);
138         for(int i=1;i<=n;i++) scanf("%d",&num[i]);
139         build(1,1,n);
140 
141         while(q--)
142         {
143             char c;
144             while(c=getchar()){
145                 if(c=='A'||c=='R'||c=='Q') break;
146             }
147             if(c=='A'){
148                 int v,l;
149                 scanf("%d %d",&v,&l);
150                 update(1,l,v);
151             }
152             if(c=='R'){
153                 int a,l,r;
154                 scanf("%d %d %d",&a,&l,&r);
155                 update(1,l,r,a);
156             }
157             if(c=='Q'){
158                 int l,r;
159                 scanf("%d %d",&l,&r);
160                 printf("%d
", query(1,l,r));
161             }
162         }
163     }
164 
165     return 0;
166 }