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:Duc
Ngày:2008-10-28
Thời gian chạy:0.850s
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
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.
2017-11-24 02:19:39
nhật hào sạch
2017-10-02 04:16:22
tle tại m gà thôi Thông ạ
2017-10-02 03:47:24
thay int = long mà tele mãi @@
2013-08-03 11:46:57 VOJ Team
Đã add thêm test & rejudge
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.