KQUERY2 - K-query II

Giới hạn
  • Thời gian: 0.85s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Truy vấn-k II

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 ≤ 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 1 , a 2 , ..., a n (1 ≤ a i ≤ 10 4 ).
  • 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 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 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10 4 ) 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

  • Người up: paulmcvn
  • Nguồn bài: © VNOI