KQUERY2  Kquery II
English  Vietnamese 
Given a sequence of n numbers a_{1}, a_{2}, ..., a_{n} and a number of kqueries. Besides, you are also given some modify operations.
A modify operation is a pair (i, v) which means a_{i} should be set to be v.
A kquery is a triple (i, j, k). For each kquery (i, j, k), you have to return the number of elements greater than k in the subsequence a_{i}, a_{i+1}, ..., a_{j}.
Input
 Line 1: n (1 ≤ n ≤ 30000).
 Line 2: n numbers a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{4}) representing the initial sequence.
 Line 3: q (1 ≤ q ≤ 200000), the number of operations.
 In the next q lines, the first number of each line contains a flag value which is either 0 or 1. A flag 0 follows by 2 numbers i and v (1 ≤ i ≤ n, 1 ≤ v ≤ 10^{4}) representing a modify operation. A flag 1 follows by 3 numbers i, j and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10^{4}) representing a kquery.
Output
 For each kquery (i, j, k), print the number of elements greater than k in the subsequence a_{i}, a_{i+1}, ..., a_{j} in a single line.
Example
Input 5 5 1 2 3 4 6 1 2 4 1 0 4 10 1 4 4 4 0 3 1 0 1 2 1 1 5 2 Output 2 1 2
hide comments
dancooper:
20191230 18:38:43
Share my own experience.


tucanhminh:
20191214 08:42:07
Segment tree + vector + BIT + fast I/O => AC in ~1.48s 

humbletheif:
20180626 15:31:14
I am getting TLE even after using sqrt decomposition..need help 

sharanx:
20171207 08:57:02
decomposition+BIT=AC in one go :) 

Puneet:
20170624 06:38:17
Is there any way to solve this and KQUERY using Segment tree without offline queries.


Min_25:
20160813 07:42:40
Should be moved to classical. 

kliu31415:
20160122 06:00:30
Is there any way to request this problem to be moved? This is definitely at least a medium difficulty problem (I think this requires knowledge of a 2D range tree). 

Scape:
20151103 17:07:27
This should not be in tutorial. 

:
20150212 11:14:08
Why is this problem in tutorial ? 
Added by:  Jimmy 
Date:  20081028 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  © VNOI 