KQUERY2 - K-query II

Truy vấn-k II

Cho một dãy n phần tử a1, a2, ..., an 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à ai 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 ai, ai+1, ..., aj.

Dữ liệu

  • Dòng 1: n (1 ≤ n ≤ 30000).
  • Dòng 2: n số a1, a2, ..., an (1 ≤ ai ≤ 104).
  • 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 ≤ 104) 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 ≤ 104) 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 ai, ai+1, ..., aj 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 

Đượ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

hide comments
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
2017-12-18 02:48:06
Bài này các bạn nên dùng thuật toán BIT + Alpha Road là Accepted nha.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.