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<bits/stdc++.h>
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,127,sizeof(a));
#define TS printf("111111\n");
#define FOR(i,a,b) for( int i=a;i<=b;i++)
#define FORJ(i,a,b) for(int i=a;i>=b;i--)
#define READ(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inf 100000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//****************************************
#define maxn 1000000+5 bool P[];
ll a[+];
struct ss
{
ll l,r,v,tag,sum;
}tr[maxn*]; void pushdown(int k)
{
if(!tr[k].tag)return;
if(tr[k].l==tr[k].r){
tr[k].v=tr[k].tag;
if(!P[tr[k].v])
tr[k].sum=;
else tr[k].sum=;
}
else {
if(!P[tr[k].tag])tr[k].sum=tr[k].r-tr[k].l+;
else {tr[k].sum=;}
tr[k<<].tag=tr[k].tag;
tr[k<<|].tag=tr[k].tag;
}
tr[k].tag=;
}
void pushup(int k)
{
pushdown(k<<);
pushdown(k<<|);
tr[k].sum=tr[k<<].sum+tr[k<<|].sum;
}
void build(int k,int s,int t)
{
tr[k].l=s;
tr[k].r=t;
tr[k].tag=;
tr[k].sum=;
if(s==t)
{tr[k].v=a[s];if(!P[a[s]])tr[k].sum=;else tr[k].sum=;return;}
int mid=(s+t)>>;
build(k<<,s,mid);
build(k<<|,mid+,t);
pushup(k);
}
void add(int k,int x,int y)
{
pushdown(k);
if(x==tr[k].l&&tr[k].l==tr[k].r)
{
tr[k].v+=y;
if(!P[tr[k].v])
tr[k].sum=;
else tr[k].sum=;
return ;
}
int mid=(tr[k].l+tr[k].r)>>;
if(x<=mid)
add(k<<,x,y);
else add(k<<|,x,y);
pushup(k);
}
void update(int k,int x,int y,int c)
{
pushdown(k);
if(x==tr[k].l&&y==tr[k].r)
{
tr[k].tag=c;
return ;
}
int mid=(tr[k].l+tr[k].r)>>;
if(y<=mid)update(k<<,x,y,c);
else if(x>mid)update(k<<|,x,y,c);
else {
update(k<<,x,mid,c);
update(k<<|,mid+,y,c);
}
pushup(k);
}
ll ask(int k,int x,int y)
{
pushdown(k);
if(x==tr[k].l&&y==tr[k].r)
{
return tr[k].sum;
}
int mid=(tr[k].l+tr[k].r)>>;
if(y<=mid)return ask(k<<,x,y);
else if(x>mid)return ask(k<<|,x,y);
else {
return (ask(k<<,x,mid)+ask(k<<|,mid+,y));
} pushup(k);
}
int main()
{
P[]=;
for(int i=;i<=;i++)
{
if(!P[i])
for(int j=i+i;j<=;j+=i)
P[j]=;
}
ll n,q,c;
int T=read();
while(T--)
{
scanf("%lld%lld",&n,&q);
FOR(i,,n)
{
scanf("%lld",&a[i]);
}
char ch[];
ll x,y;
build(,,n);
FOR(i,,q)
{
scanf("%s%lld%lld",&ch,&x,&y);
if(ch[]=='A')
{
add(,y,x);
}
else if(ch[]=='R')
{
scanf("%lld",&c);
update(,y,c,x);
}
else if(ch[]=='Q')
{
printf("%lld\n",ask(,x,y));
}
}
}
return ;
}
挫挫的代码