Submit solution
Points:
1.01 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một dãy ~n~ phần tử ~a_{1}~, ~a_{2}~, ..., ~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~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~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}~.
Input
- Dòng ~1~: ~n~ (~1~ ~\leq~ ~n~ ~\leq~ ~30000~).
- Dòng ~2~: ~n~ số ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ (~1~ ~\leq~ ~a_{i}~ ~\leq~ ~10^{4}~).
- Dòng ~3~: ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~200000~), số truy vấn và cập nhật.
- ~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~ ~\leq~ ~i~ ~\leq~ ~n~, ~1~ ~\leq~ ~v~ ~\leq~ ~10^{4}~) 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~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~, ~1~ ~\leq~ ~k~ ~\leq~ ~10^{4}~) cho biết một truy vấn-k.
Output
- 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.
Sample 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
Sample Output
2
1
2
Comments
Có bạn nào làm bằng merge sort tree không, mình xin code đọc với, mình bị tle
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
K-Query 2 làm như sau:
Cảm ơn bạn 🥰
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.