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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#define VI vector<int>
#define VP vector<Point>
#define pr pair<int,int>
#define LL long long
#define fread() freopen("../in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;
const int Max = 1e7;
const int Maxn = 100000;
typedef struct Tree
{
int num;//记录所在区间的素数的个数
int lazy;//标记所在的区间有没有被整体更新
} Tree;
int vis[Max+1000];
Tree Tr[Maxn*5];
int a[Maxn+100];
void init()//素数表
{
memset(vis,0,sizeof(vis));
int m= (int)sqrt(Max);
vis[0]=1;
vis[1]=1;
for(LL i=2; i<=m; i++)
{
if(!vis[i])
{
for(LL j=i*i; j<=Max; j+=i)
{
vis[j]=1;
}
}
}
}
void Pushup(int st,int L,int R)//线段树区间向上更新
{
if(Tr[st<<1|1].lazy&&Tr[st<<1].lazy&&Tr[st<<1|1].lazy==Tr[st<<1].lazy)//
{
Tr[st].lazy=Tr[st<<1].lazy;
}
else
{
Tr[st].lazy=0;
}
Tr[st].num=Tr[st<<1].num+Tr[st<<1|1].num;
}
void Pushdown(int st,int L,int R)//线段树区间向下更新
{
if(Tr[st].lazy&&L!=R)
{
int mid =(L+R)>>1;
Tr[st<<1].lazy=Tr[st<<1|1].lazy=Tr[st].lazy;
if(Tr[st].num)
{
Tr[st<<1|1].num=R-mid;
Tr[st<<1].num=mid+1-L;
}
else
{
Tr[st<<1|1].num=Tr[st<<1].num=0;
}
Tr[st].lazy=0;
}
}
void Build(int L,int R,int st)//初始化线段树
{
Tr[st].lazy=0;
Tr[st].num=0;
if(L==R)
{
Tr[st].lazy=a[L];
Tr[st].num=(!vis[a[L]]);
return ;
}
int mid=(L+R)>>1;
Build(L,mid,st<<1);
Build(mid+1,R,st<<1|1);
Pushup(st,L,R);
}
void Add(int L,int R,int st,int s,int d)//单点更新
{
Pushdown(st,L,R);
if(L==s&&R==s)
{
Tr[st].lazy+=d;
Tr[st].num=(!vis[Tr[st].lazy]);
return ;
}
int mid =(L+R)>>1;
if(s<=mid)
{
Add(L,mid,st<<1,s,d);
}
else
{
Add(mid+1,R,st<<1|1,s,d);
}
Pushup(st,L,R);
}
void Update(int L,int R,int st,int l,int r,int d)//区间更新
{
if(L>r||R<l)
{
return ;
}
if(L>=l&&R<=r)
{
Tr[st].lazy=d;
Tr[st].num=(!vis[d])*(R-L+1);
return ;
}
Pushdown(st,L,R);
int mid = (L+R)>>1;
if(l<=mid)
{
Update(L,mid,st<<1,l,r,d);
}
if(r>mid)
{
Update(mid+1,R,st<<1|1,l,r,d);
}
Pushup(st,L,R);
}
int Query(int L,int R,int st,int l,int r)//区间查询
{
if(L>r||R<l)
{
return 0;
}
Pushdown(st,L,R);
if(L>=l&&R<=r)
{
return Tr[st].num;
}
int mid=(L+R)>>1;
int sum=0;
if(l<=mid)
{
sum+=Query(L,mid,st<<1,l,r);
}
if(r>mid)
{
sum+=Query(mid+1,R,st<<1|1,l,r);
}
Pushup(st,L,R);
return sum;
}
int main()
{
int T,n,q;
int l,r,s,d;
char op[3];
init();
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&q);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
}
Build(1,n,1);
while(q--)
{
scanf("%s",op);
if(op[0]=='A')
{
scanf("%d %d",&d,&s);
Add(1,n,1,s,d);
}
else if(op[0]=='Q')
{
scanf("%d %d",&l,&r);
printf("%d\n",Query(1,n,1,l,r));
}
else if(op[0]=='R')
{
scanf("%d %d %d",&d,&l,&r);
Update(1,n,1,l,r,d);
}
}
}
return 0;
}