trang chủ / đề bài / icpc25_mb_j

Điệu valse

Đề bài

Mô tả

Là những vũ công xuất sắc, Katharina và bạn được mời mở màn điệu valse trong buổi dạ hội thường niên của Cộng đồng những người vụng về khét tiếng. Sau nhiều giờ luyện tập, cả hai đều tự tin vào kỹ năng của mình. Tuy nhiên, đúng như tên gọi, các vũ công khác có thể vụng về và nhầm bạn nhảy của người khác là của mình, nhất là trên một sàn nhảy hỗn loạn.

Năm nay, điệu valse mở màn được biểu diễn như sau: đầu tiên, tất cả n vũ công đứng thành một hàng. Mỗi vũ công được phát một số hiệu (ID) để khán giả có thể theo dõi.

Sau đó, tại một số thời điểm, các vũ công ở vị trí từ l đến r thực hiện một điệu nhảy vòng k bước. Nghĩa là nếu trước điệu nhảy, ID của n vũ công theo thứ tự là mảng b1,…,bn, thì sau điệu nhảy ID của họ trở thành

b1,…,bl−1,br−k+1,br−k+2,…,br−1,br,bl,bl+1,…,br−k,br+1,…,bn.

Khi mọi người cùng nhảy, bạn không muốn mất dấu người bạn nhảy quý giá của mình (nếu không, cô ấy sẽ rất giận bạn sau đó). Nhưng có ba vấn đề:

  • Bạn vụng về, nên không thể theo dõi cô ấy trong lúc nhảy;
  • Các vũ công khác cũng vụng về, nên dù trong mắt khán giả các ID có vẻ nhất quán, một vũ công có thể lại mang ID của người khác (đó là lý do cần có ID ngay từ đầu). Vì vậy, ngay cả ID của Katharina cũng có thể thay đổi.
  • Ban tổ chức cũng vụng về, nên có thể có nhiều vũ công cùng một ID.

Biết vậy, thỉnh thoảng Katharina sẽ yêu cầu bạn nhận ra cô ấy. Cô ấy đưa cho bạn ba số l, r và k, nghĩa là ID của cô ấy là số nhỏ thứ k trong các ID của các vũ công ở vị trí từ l đến r trong hàng. Nói cách khác, nếu ID của n vũ công là mảng b1,…,bn, thì ID của cô ấy là số nhỏ thứ k trong các số bl,…,br.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên n và q: số vũ công và số thao tác.
  • Dòng thứ hai gồm n số nguyên a1,…,an: ID ban đầu của các vũ công theo thứ tự trong hàng.
  • q dòng tiếp theo, dòng thứ i gồm bốn số nguyên ti, li, ri, ki. Giả sử trước thao tác này, ID của các vũ công theo thứ tự là b1,b2,…,bn.
    • Nếu ti=1: các vũ công ở vị trí từ li đến ri thực hiện điệu nhảy vòng ki bước, tức là sau đó ID của các vũ công là b1,…,bl−1,br−k+1,…,br,bl,…,br−k,br+1,…,bn.
    • Nếu ti=2: Katharina muốn bạn nhận ra cô ấy; ID của cô ấy là số nhỏ thứ ki trong bli,…,bri.

Dữ liệu ra

Với mỗi thao tác loại 2, in ra ID của Katharina trên một dòng.

Ràng buộc

  • 1≤n,q≤105
  • 1≤ai≤109
  • ti∈{1,2}, 1≤li≤ri≤n, 1≤ki≤ri−li+1

Ví dụ

Input Output Giải thích
10 10
10 5 7 5 1 9 8 1 10 1
1 6 10 1
2 1 4 2
2 3 7 3
1 9 10 1
2 5 8 2
2 2 4 1
1 4 10 4
2 6 8 1
1 1 10 9
2 1 3 1
5
5
1
5
1
5
Sau thao tác đầu tiên, mảng là 10,5,7,5,1,1,9,8,1,10. Số nhỏ thứ 2 trong 10,5,7,5 là 5.
5 5
3 1 2 1 3
2 1 5 3
1 1 5 2
2 1 2 2
1 2 4 1
2 3 5 1
2
3
2
Ví dụ bổ sung. Sau thao tác thứ hai mảng là 1,3,3,1,2; sau thao tác thứ tư là 1,1,3,3,2.

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