JOI 2025 - Bubble Sort Machine

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2200 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

JOI-kun, một nhà nghiên cứu thuật toán, đã phát triển một thiết bị có tên Máy sắp xếp nổi bọt.

Máy thao tác trên dãy số nguyên \(a=(a_1,a_2,\ldots,a_N)\) có độ dài \(N\). Khi khởi động, máy nhận giá trị ban đầu \(A_i\) cho mỗi phần tử \(a_i\) (\(1\le i\le N\)). Mỗi lần nhấn nút 1, máy lần lượt xét \(i=1,2,\ldots,N-1\); nếu \(a_i>a_{i+1}\) thì hoán đổi giá trị của \(a_i\) và \(a_{i+1}\).

Để chiếc máy hấp dẫn hơn, JOI-kun bổ sung nút 2. Khi nhấn nút này và nhập hai số nguyên \(l,r\) thỏa mãn \(1\le l\le r\le N\), máy xuất giá trị \(a_l+a_{l+1}+\cdots+a_r\).

Cho các giá trị ban đầu của dãy và trình tự thao tác trên máy, hãy tính các giá trị mà máy xuất ra khi nhấn nút 2.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
A_1 A_2 ... A_N
Q
(Truy vấn 1)
(Truy vấn 2)
...
(Truy vấn Q)

\(Q\) là số thao tác. Truy vấn thứ \(j\) (\(1\le j\le Q\)) gồm các số nguyên cách nhau bởi dấu cách. Gọi \(T_j\) là số đầu tiên trên dòng:

  • 1: dòng không chứa số nào khác; thao tác thứ \(j\) là nhấn nút 1.
  • 2 L_j R_j: thao tác thứ \(j\) là nhấn nút 2 với hai số \(L_j,R_j\).

Dữ liệu ra

Với mỗi \(j\) thỏa mãn \(T_j=2\), xuất giá trị máy trả về trên một dòng riêng, theo đúng thứ tự truy vấn.

Ràng buộc

  • \(2\le N\le 500\,000\).
  • \(1\le A_i\le 10^9\) với \(1\le i\le N\).
  • \(1\le Q\le 500\,000\).
  • \(T_j\in\{1,2\}\) với \(1\le j\le Q\).
  • Nếu \(T_j=2\) thì \(1\le L_j\le R_j\le N\).
  • Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

  1. \(5\) điểm: Có nhiều nhất \(10\) chỉ số \(j\) (\(1\le j\le Q\)) thỏa mãn \(T_j=1\).
  2. \(11\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\); với mọi \(j\) có \(T_j=2\), \(L_j=R_j=1\).
  3. \(15\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\); \(1\le A_i\le 2\) với mọi \(1\le i\le N\).
  4. \(23\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\); với mọi \(j\) có \(T_j=2\), \(L_j=R_j\).
  5. \(29\) điểm: \(N\le 150\,000\), \(Q\le 150\,000\).
  6. \(17\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
4
5 3 5 2
6
2 1 3
1
2 1 1
2 2 4
1
2 1 2
Output 
13
3
12
5
Giải thích

Ban đầu, máy nhận \(a_1=5\), \(a_2=3\), \(a_3=5\), \(a_4=2\), nên \(a=(5,3,5,2)\). Các thao tác diễn ra như sau:

  1. Nhấn nút 2 với \(l=1,r=3\). Máy xuất \(a_1+a_2+a_3=13\).
  2. Nhấn nút 1. Với \(i=1\), do \(a_1>a_2\), máy hoán đổi hai giá trị và thu được \(a=(3,5,5,2)\). Với \(i=2\), điều kiện \(a_2>a_3\) không đúng nên dãy không đổi. Với \(i=3\), do \(a_3>a_4\), máy hoán đổi và thu được \(a=(3,5,2,5)\).
  3. Nhấn nút 2 với \(l=1,r=1\). Máy xuất \(a_1=3\).
  4. Nhấn nút 2 với \(l=2,r=4\). Máy xuất \(a_2+a_3+a_4=12\).
  5. Nhấn nút 1. Với \(i=1\), điều kiện \(a_1>a_2\) không đúng nên dãy không đổi. Với \(i=2\), do \(a_2>a_3\), máy hoán đổi và thu được \(a=(3,2,5,5)\). Với \(i=3\), điều kiện \(a_3>a_4\) không đúng nên dãy không đổi.
  6. Nhấn nút 2 với \(l=1,r=2\). Máy xuất \(a_1+a_2=5\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,5,6\).

Ví dụ 2

Input 
5
1 1 2 1 2
5
2 2 3
1
2 2 4
1
2 2 4
Output 
3
4
4
Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,3,5,6\).

Nguồn

JOI Open Contest 2025, bài Bubble Sort Machine, tác giả Masaki Nishimoto.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: