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
题解：线段树的单点更新，区间修改，区间查询
写的很挫
///1085422276 #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 "); #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=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } //**************************************** #define maxn 1000000+5 bool P[10000101]; ll a[1000000+5]; struct ss { ll l,r,v,tag,sum; }tr[maxn*5]; 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=1; else tr[k].sum=0; } else { if(!P[tr[k].tag])tr[k].sum=tr[k].r-tr[k].l+1; else {tr[k].sum=0;} tr[k<<1].tag=tr[k].tag; tr[k<<1|1].tag=tr[k].tag; } tr[k].tag=0; } void pushup(int k) { pushdown(k<<1); pushdown(k<<1|1); tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum; } void build(int k,int s,int t) { tr[k].l=s; tr[k].r=t; tr[k].tag=0; tr[k].sum=0; if(s==t) {tr[k].v=a[s];if(!P[a[s]])tr[k].sum=1;else tr[k].sum=0;return;} int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,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=1; else tr[k].sum=0; return ; } int mid=(tr[k].l+tr[k].r)>>1; if(x<=mid) add(k<<1,x,y); else add(k<<1|1,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)>>1; if(y<=mid)update(k<<1,x,y,c); else if(x>mid)update(k<<1|1,x,y,c); else { update(k<<1,x,mid,c); update(k<<1|1,mid+1,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)>>1; if(y<=mid)return ask(k<<1,x,y); else if(x>mid)return ask(k<<1|1,x,y); else { return (ask(k<<1,x,mid)+ask(k<<1|1,mid+1,y)); } pushup(k); } int main() { P[1]=1; for(int i=2;i<=10000000;i++) { if(!P[i]) for(int j=i+i;j<=10000000;j+=i) P[j]=1; } ll n,q,c; int T=read(); while(T--) { scanf("%lld%lld",&n,&q); FOR(i,1,n) { scanf("%lld",&a[i]); } char ch[30]; ll x,y; build(1,1,n); FOR(i,1,q) { scanf("%s%lld%lld",&ch,&x,&y); if(ch[0]=='A') { add(1,y,x); } else if(ch[0]=='R') { scanf("%lld",&c); update(1,y,c,x); } else if(ch[0]=='Q') { printf("%lld ",ask(1,x,y)); } } } return 0; }