Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
|
|||||||
2024-10-24 21:40:07
I used sqrt decomposition technique .I used vector of multisets first but i had time limit , and when i used vector of vectors with sort in each update it passed , i dont know why because i think it's same complexity which is O(sqrt(n)*log(n)*q) Last edit: 2024-10-24 21:41:02 |
|||||||
2024-07-22 09:09:25
WA in 10 please hack |
|||||||
2023-11-15 17:02:38
Compilation error in one go . |
|||||||
2023-04-13 08:32:29
failing testcase 10 : Try this one : 10 1 2 3 4 5 6 7 8 9 10 10 0 1 1 1 0 1 2 1 0 1 3 1 0 1 4 1 0 1 5 1 0 1 6 1 0 1 7 1 0 1 8 1 0 1 9 1 0 1 10 1 and also, are you sure, that you are considering greater values than C after applying BS..? |
|||||||
2023-02-18 15:10:45
using sqrt decomposition and some evil technology..... finally solved this problem :) |
|||||||
2022-09-28 13:49:00
I use sqrt decompose and binary search but the code fails on test case #10. Please help Here is my code ... <snip> [Simes]: Read the footer - Don't post source code here, use the forum. Last edit: 2022-09-28 21:36:03 |
|||||||
2021-12-21 11:27:14
use sqrt decomposition and for each block u can use a vector |
|||||||
2021-12-10 06:31:21
Please help me debug my code. WA in 10. I have taken all the cases when startblock=endblock. Can someone point out what are the mistakes that is causing WA in 10. |
|||||||
2021-06-23 18:53:01
Time limit is more than 2sec. Square Root Decomposition will pass. No need to use PBDS as I solved without it. Last edit: 2021-06-23 18:53:34 |
|||||||
2021-04-27 09:13:37
Square root decomposition + policy based ds |