正文

ZOJ 3911 Prime Query（线段树）

IP云
IP云V管理员/1 阅读
06/16
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

1
5 10
1 2 3 4 5
A 3 1
Q 1 3
R 5 2 4
A 1 1
Q 1 1
Q 1 2
Q 1 4
A 3 5
Q 5 5
Q 1 5

Sample Output

2
1
2
4
0
4

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

【题意】：

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

【解题思路】：

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

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mid(a,b) ((a+b)>>1)
#define LL int
#define maxn 110000
#define IN freopen("in.txt","r",stdin);
using namespace std; char is_prime[maxn*];
void sieve()
{
int m=(int)sqrt((maxn*)+0.5);
fill(is_prime,is_prime+(maxn*),);
is_prime[]=is_prime[]=;
for(int i=;i<=m;i++) if(is_prime[i])
for(int j=i*i;j<(maxn*);j+=i) is_prime[j]=;
} int n,q;
LL num[maxn];
struct Tree
{
int left,right;
LL sum;
LL val,lazy;
}tree[maxn<<]; /*递归建树*/
void build(int i,int left,int right)
{
tree[i].left=left;
tree[i].right=right;
tree[i].lazy=; if(left==right){
tree[i].val=num[left];
tree[i].sum=(is_prime[num[left]]? :);
return ;
} int mid=mid(left,right); build(i<<,left,mid);
build(i<<|,mid+,right); tree[i].sum=tree[i<<].sum+tree[i<<|].sum;
} /*区间修改，标记下传：每当访问到当前结点的子节点时，下传标记*/
void pushdown(int i)
{
if(tree[i].lazy){
int tmp = (is_prime[tree[i].lazy]? :);
tree[i<<].val=tree[i].lazy;
tree[i<<|].val=tree[i].lazy;
tree[i<<].lazy=tree[i].lazy;
tree[i<<|].lazy=tree[i].lazy;
tree[i<<].sum=(tree[i<<].right-tree[i<<].left+)*tmp;
tree[i<<|].sum=(tree[i<<|].right-tree[i<<|].left+)*tmp;
tree[i].lazy=; /*下传后清零*/
}
} /*区间修改，d为改变量*/
void update(int i,int left,int right,LL d)
{
if(tree[i].left==left&&tree[i].right==right)
{
int tmp = (is_prime[d]? :);
tree[i].sum=(right-left+)*tmp;
tree[i].val=d;
tree[i].lazy=d;
return ;
} pushdown(i); int mid=mid(tree[i].left,tree[i].right); if(right<=mid) update(i<<,left,right,d);
else if(left>mid) update(i<<|,left,right,d);
else
{
update(i<<,left,mid,d);
update(i<<|,mid+,right,d);
} tree[i].sum=tree[i<<].sum+tree[i<<|].sum;
} /*单点修改，d为改变量*/
void update(int i,int x,LL d)
{
if(tree[i].left==tree[i].right){
tree[i].val+=d;
tree[i].sum=(is_prime[tree[i].val]? :);
return;
} pushdown(i);
int mid=mid(tree[i].left,tree[i].right); if(x<=mid) update(i<<,x,d);
else update(i<<|,x,d); tree[i].sum=tree[i<<].sum+tree[i<<|].sum;
} /*区间结果查询*/
LL query(int i,int left,int right)
{
if(tree[i].left==left&&tree[i].right==right)
return tree[i].sum; pushdown(i); int mid=mid(tree[i].left,tree[i].right); if(right<=mid) return query(i<<,left,right);
else if(left>mid) return query(i<<|,left,right);
else return query(i<<,left,mid)+query(i<<|,mid+,right);
} int main(int argc, char const *argv[])
{
//IN; sieve();
int t;scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&q);
for(int i=;i<=n;i++) scanf("%d",&num[i]);
build(,,n); while(q--)
{
char c;
while(c=getchar()){
if(c=='A'||c=='R'||c=='Q') break;
}
if(c=='A'){
int v,l;
scanf("%d %d",&v,&l);
update(,l,v);
}
if(c=='R'){
int a,l,r;
scanf("%d %d %d",&a,&l,&r);
update(,l,r,a);
}
if(c=='Q'){
int l,r;
scanf("%d %d",&l,&r);
printf("%d\n", query(,l,r));
}
}
} return ;
}