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:

  1. 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
  2. 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
hackerbhaiya: 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
noobmaster__69: 2021-04-27 09:13:37

Square root decomposition + policy based ds

adia: 2021-01-17 22:45:32

compilation error in one go <3

dharan1011: 2020-09-21 15:20:20

AC in one GO.

prabal08: 2020-08-12 11:38:29

Any test cases guys?

brandonbreyers: 2020-07-18 12:44:56

I was getting wa for test case 10 again and again, realised that i had to handle the case of the 1st query where a and b could be in the same block

leetcode07: 2020-07-10 14:46:27

I use sqrt decompose and policy-based c++ ds but the code fails on test case #10. Please help

pratyushmj1: 2020-06-03 15:45:17

A story about Test cases,
1..ok 2..ok 3...ohhyeaa...4...ohhyeaa...5...ohhyeaa...7...ohhyeaa......10 WA . :D

harshraj22aug: 2020-01-02 09:41:15

Last edit: 2020-01-02 10:19:23
scolar_fuad: 2019-11-09 17:34:18

sqrt decompose + binary search ...
some tricks you have to follow


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