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
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...

anurag garg: 2014-05-09 15:13:04

nice....

Ryuzaki: 2014-02-18 11:55:29

Will a TREAP won't work in this case ??


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