Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

## KQUERY2 - K-query II

 English Vietnamese

Given a sequence of n numbers a1, a2, ..., an and a number of k-queries. Besides, you are also given some modify operations.

A modify operation is a pair (i, v) which means ai should be set to be v.

A k-query is a triple (i, j, k). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ..., aj.

### Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 104) 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 ≤ 104) representing a modify operation. A flag 1 follows by 3 numbers i, j and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 104) representing a k-query.

### Output

• For each k-query (i, j, k), print the number of elements greater than k in the subsequence ai, ai+1, ..., aj 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
```

 Được gửi lên bởi: Jimmy Ngày: 2008-10-28 Thời gian chạy: 1s Giới hạn mã nguồn: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Ngôn ngữ cho phép: Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET Nguồn bài: © VNOI

2021-05-20 14:38:30
test yếu quá :(
cập nhật 10^4 vẫn ac
-ppy

Last edit: 2021-05-23 13:37:59
2020-09-13 12:48:34
MST build kiểu gì cũng quá time T.T xuống dưới này nghe mấy ông chỉ chia căn + BIT mới AC
https://ideone.com/hOW54d
2020-06-27 13:41:59
Tham khảo:
Solution: http://megaurl.in/4jStcX1
Code: http://megaurl.in/5Rt3wn
2020-04-10 10:28:58
bon dau buoi ngu hoc deo chiu suy nghi moi xuong cmt De vai roi noi thuat toan
2020-04-07 19:53:42
chia căn + BIT =>> TLE mà @@ =.=
2020-04-06 11:01:58
oh sh!t !!! sao tớ 1.55s vẫn AC thế này
2019-09-15 18:23:21
nhân phẩm :)
cùng một code nộp lần 1 tle, lần 2 ac.
my code : http://ideone.com/vhRgMd
2019-08-15 20:33:45
chia căn + BIT =>> AC nhé anh em :v
2018-08-20 11:13:45
chia làm căn(n) block + BIT và accepted một cách bất ngờ, O(q.căn(n).log(10000)) ...
2018-08-17 07:50:58
Dễ vãi.

Last edit: 2018-12-18 05:57:37