trang chủ / đề bài / dhbb26_dx08_11_c

Số nhỏ thứ k

Đề bài

Mô tả

Tại thành phố nọ, có n cột đá, cột đá thứ i có chỉ số kỹ năng ai. Bạn được giao nhiệm vụ xử lý q truy vấn thuộc hai loại sau đây:

  • Loại 1: 1 l v. Đây là truy vấn cập nhật: chỉ số kỹ năng của cột đá thứ l được thay đổi thành v.
  • Loại 2: 2 l r k. Đây là truy vấn báo cáo: yêu cầu tìm giá trị kỹ năng nhỏ thứ k trong đoạn các cột đá từ l đến r (tính cả l và r).

Dữ liệu vào

  • Dòng đầu tiên gồm một số nguyên dương n (1≤n≤105);
  • Dòng tiếp theo chứa n số nguyên dương a1,a2,…,an (1≤ai≤109), chỉ số kỹ năng ban đầu;
  • Dòng tiếp theo chứa một số nguyên dương q (1≤q≤105);
  • q dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại:
    • 1 l v (1≤l≤n, 1≤v≤109);
    • 2 l r k (1≤l≤r≤n, 1≤k≤r−l+1).

Dữ liệu ra

Với mỗi truy vấn Loại 2, in ra kết quả là một số nguyên duy nhất trên một dòng.

Ràng buộc

  • 1≤n,q≤105.
  • 1≤ai,v≤109.

Subtasks

  • Subtask 1 (15% số điểm): n≤103, q≤103.
  • Subtask 2 (25% số điểm): n≤105, q≤105 và không có truy vấn Loại 1.
  • Subtask 3 (15% số điểm): n≤105, q≤105 và mọi truy vấn Loại 2 có k≤10.
  • Subtask 4 (25% số điểm): n≤5·104, q≤5·104, ai,v≤5·103.
  • Subtask 5 (20% số điểm): n≤105, q≤105 và không có ràng buộc bổ sung.

Ví dụ

Input Output Giải thích
5
1 2 3 4 5
3
2 2 4 2
1 3 6
2 2 4 2
3
4
Đoạn [2,4] ban đầu là (2,3,4), số nhỏ thứ hai là 3. Sau khi a3=6, đoạn là (2,6,4), số nhỏ thứ hai là 4.
4
5 5 1 5
3
2 1 4 1
2 1 4 2
2 1 4 4
1
5
5
Ví dụ thêm (không có trong đề gốc). Sắp xếp đoạn được (1,5,5,5); các giá trị bằng nhau được tính riêng.
1
7
3
2 1 1 1
1 1 3
2 1 1 1
7
3
Ví dụ thêm (không có trong đề gốc).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0