PRMQUER - Prime queries
You are given a simple task.
Given a sequence A[i] with N numbers such that 1 <= i <= N. You have to perform Q operations on a given set of numbers.
Operations:
A V l
, Add the value V to element with index l.R a l r
, Replace all the elements of sequence with index i such that l <= i <= r with a.Q l r
, Print the number of elements with index i such that l <= i <= r and A[i] is prime number and A[i] <= 10^7.
No number in the 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 and Q as number of operations to be performed. Second line contains N initial 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
neach_joup:
2022-10-21 02:49:18
Long long!!! Last edit: 2022-10-21 02:49:47 |
|
thesky233:
2022-10-01 14:04:17
notice that operation 3 says that <=10^7...
|
|
sabkx:
2022-04-29 14:18:51
ODT trash this |
|
yaseenmollik:
2020-08-11 03:14:07
After tons of WA finally got it accepted! Nice problem. |
|
setsugesuka:
2019-10-03 12:09:32
ODT can solve this problem easily.. |
|
sherlock11:
2018-06-29 06:09:05
read the 3rd query carefully it says <=10^7.....if u ignore this then AC will ignore u..:) |
|
hackerwizard:
2018-05-19 18:39:29
Nice question learned something new |
|
sultania23:
2017-03-19 05:49:04
properly look input format and range otherwise runtime error or wrong answer..
|
|
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? |
Added by: | Rishav Goyal |
Date: | 2014-04-16 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own |