GIVEAWAY - Give Away
You are given a 1-indexed array X, consisting of N integers, and a set of Q queries. There are two kinds of queries:
- 0 a b c
Here you are required to return the number of elements with indices in [a,b] greater than or equal to c - 1 a b
Here you are required to change the ath element of array to b.
Input Format:
First line contains N, the number of elements in the array X. The next line contains N space separated integers representing the elements of X. The third line of input contains a single integer, Q, the number of queries. The next Q lines of input each contain queries of two kinds as described above.
Output Format:
Q lines with the ith line contains the answer for the ith query
Constraints:
1 ≤ N ≤ 5*10^5
1 ≤ Q ≤ 10^5
1 ≤ X[i] ≤ 10^9
1 ≤ a ≤ b ≤ N for query type 0
1 ≤ a ≤ 10^5, 1 < b ≤ 10^9 for query type 1
1 ≤ c ≤ 10^9
Example
Sample Input: 5 1 2 3 4 5 3 0 1 5 10 1 2 20 0 1 3 10 Sample Output: 0 1
Problem Setter: Pulkit Goel and Vidit Gupta
hide comments
joe85123:
2019-03-06 10:50:57
toolkit's output is wrong for this problem, don't get confused. |
|
bpsr41434:
2019-01-17 20:02:17
are all the elements of array and the update values distinct?
|
|
kenny_sc0pe:
2018-07-13 15:51:46
Array consists of distinct integers only... |
|
madhur4127:
2018-02-28 14:23:47
1.72s with sqrt decomposition |
|
karan_batra:
2017-11-29 20:32:55
Same as RACETIME |
|
kejriwal:
2016-01-13 07:18:40
new concept learnt :) !!! amazing problem :D |
|
ashish kumar:
2016-01-02 10:51:48
I am using segment tree+AVL tree and O(log^2N) for query and O(logN) for update. But its giving TLE on 10th test case. And also it got accepted on codechef. Last edit: 2016-01-02 10:54:15 |
|
pikku:
2014-10-05 16:55:00
Even using Segment tree Getting TLE @ 10th test case.. |
|
Archit Jain:
2014-07-18 21:46:30
TLE using segmented tree Last edit: 2014-07-18 21:51:44 |
|
Bhavik:
2014-06-02 20:10:18
what ds to use?any suggestions... |
Added by: | darkshadows |
Date: | 2014-01-28 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |