Giải bài trực tuyến

Truy vấn-k II

Cho một dãy n phần tử a₁, a₂, ..., a_n và một số các truy vấn-k. Ngoài ra còn có một số thao tác cập nhật.

Một thao tác cập nhật là một cặp (i, v) nghĩa là a_i cần được gán giá trị v.

Một truy vấn-k là một bộ ba (i, j, k) (1 ≤ i ≤ j ≤ n).

Với mỗi truy vấn-k (i, j, k), bạn phải trả về số phần tử lớn hơn k nằm trong dãy con a_i, a_i+1, ..., a_j.

Dữ liệu

• Dòng 1: n (1 ≤ n ≤ 30000).
• Dòng 2: n số a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁴).
• Dòng 3: q (1 ≤ q ≤ 200000), số truy vấn-k.
• q dòng tiếp theo, số đầu tiên trong mỗi dòng là 0 hoặc 1. Số 0 theo sau bởi 2 số i và v (1 ≤ i ≤ n, 1 ≤ v ≤ 10⁴) cho biết một thao tác cập nhật. Số 1 theo sau bởi 3 số nguyên i, j, k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10⁴) cho biết một truy vấn-k.

Kết quả

• Với mỗi truy vấn-k (i, j, k), in ra số phần tử lớn hơn k trong dãy con a_i, a_i+1, ..., a_j trên một dòng.

Ví dụ

Dữ liệu
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  

Kết quả
2
1
2