PRMQUER - Prime queries

no tags 

You are given a simple task. Given a sequence A[i] with N numbers s.t. 1<=i<=N . You have to perform Q operations on a given set of numbers.

Operations :

1. A V l, Add the value V to element with index l .
2. R a l r, Replace all the elements of sequence with index i s.t. l<=i<=r with a .
3. Q l r, print the Number of elements with index i s.t. l<=i<=r and A[i] is prime number and A[i]<=10^7 .

No Number In sequence ever will exceed 10^9.

Constraints : 1<=N<=10^5, 1<=Q<=10^5, V<=10^3, A[i] <= 10^8 , a<=10^7,  1 <=  l <= r <=N.

Input :
First line contains N as Number of sequence elements && Q as number of operations to be performed. Second line contains Initial N elements of the sequence. After that each of the next Q lines contains one operation to be performed on the sequence.

Output :
print each value in newline as stated above.


                                                                                                                                                          Example                            
Input :                                
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

Output :
2
1
2
4
0
4


hide comments
sultania23: 2017-03-19 05:49:04

properly look input format and range otherwise runtime error or wrong answer..
nice ques.

hodobox: 2016-06-13 22:03:56

I got AC assuming 0 <= A[i] <= 2^32 at all times

Last edit: 2016-06-17 04:20:59
sachinsahoo11: 2016-06-02 22:44:16

can the numbers in the array go negative at any point?

[deleted]: 2015-02-11 09:34:06

Can V be negative ?

arjundabra: 2014-12-19 11:49:14

finally AC nice ques...

arjundabra: 2014-12-19 09:21:41

@Rishav Goyal
Can you please tell me why i am getting wrong answer on test 4.

Luis Manuel D�az Bar�n: 2014-11-11 15:57:12

Finally Accepted. This is a bit hard than this problem:
http://www.spoj.com/problems/CNTPRIME/

[Lakshman]: 2014-07-27 17:45:10

@Rishav Goyal Can you please tell me where my code fails.

Thanks

Reply(Rishav) --> check your replace operation. it's not working fine. think for a moment.

Lakshman-->You mean My range updated part is not okay?

reply(Rishav) : i can't check the code exactly, but i have a input 'R a l r,A V l, R a l r' followed by Q. and its not working fine. yeah one more thing is your output is 10 times greater the expected output. You shoud read the problem once more. Check Query Operation once more, to see what u are supposed to do.

Last edit: 2014-07-28 10:11:02
Archit Jain: 2014-07-17 10:46:03

After tonnes of wa finally AC

Last edit: 2014-07-26 14:45:33
[Lakshman]: 2014-07-17 01:29:36

@Rishav Goyal can you please tell me why I am getting segmentation fault .
Thanks.


Added by:Rishav Goyal
Date:2014-04-16
Time limit:0.649s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own