trang chủ / đề bài / icpcwf21_j

Tách và gộp dòng

Đề bài

Mô tả

Một hệ thống splitstream là một mạng không có chu trình gồm các nút, xử lý các dãy số hữu hạn. Có hai loại nút:

  • Nút tách (split) nhận một dãy số làm đầu vào và phân phối luân phiên các số cho hai đầu ra của nó. Số thứ nhất đi tới đầu ra 1, số thứ hai tới đầu ra 2, số thứ ba tới đầu ra 1, số thứ tư tới đầu ra 2, và cứ thế theo đúng thứ tự này.
  • Nút gộp (merge) nhận hai dãy số làm đầu vào và gộp luân phiên chúng thành đầu ra duy nhất. Đầu ra gồm số đầu tiên của đầu vào 1, rồi số đầu tiên của đầu vào 2, rồi số thứ hai của đầu vào 1, rồi số thứ hai của đầu vào 2, và cứ thế. Nếu một trong hai dãy đầu vào ngắn hơn dãy kia thì sau khi dãy ngắn hơn đã hết, các số còn lại của dãy dài hơn được chuyển thẳng ra đầu ra mà không cần gộp.

Ví dụ: nút tách nhận dãy 1,2,3,4,5,6,… cho ra 1,3,5,… ở đầu ra 1 và 2,4,6,… ở đầu ra 2; nút gộp nhận 1,3,5,… ở đầu vào 1 và 2,4,6,… ở đầu vào 2 cho ra 1,2,3,4,5,6,…

Toàn bộ mạng có một đầu vào duy nhất là dãy các số nguyên dương 1,2,3,…,m. Có thể truy vấn bất kỳ đầu ra nào của bất kỳ nút nào. Một truy vấn yêu cầu tìm số thứ k trong dãy số của một đầu ra cho trước, với k cho trước. Nhiệm vụ của bạn là trả lời các truy vấn đó một cách hiệu quả.

Dữ liệu vào

Dòng đầu tiên gồm ba số nguyên m, n và q, trong đó m (1≤m≤109) là độ dài dãy đầu vào, n (1≤n≤104) là số nút, và q (1≤q≤103) là số truy vấn.

n dòng tiếp theo mô tả mạng, mỗi dòng một nút. Nút tách có dạng S x y z, trong đó x, y và z lần lượt là mã của đầu vào, đầu ra thứ nhất và đầu ra thứ hai của nút. Nút gộp có dạng M x y z, trong đó x, y và z lần lượt là mã của đầu vào thứ nhất, đầu vào thứ hai và đầu ra của nút.

Các mã x, y và z là các số nguyên dương đôi một khác nhau. Đầu vào chung của cả mạng có mã 1, các mã đầu vào/đầu ra còn lại tạo thành một dãy số liên tiếp bắt đầu từ 2. Mỗi mã đầu vào khác 1 xuất hiện đúng một lần với vai trò đầu ra. Mỗi mã đầu ra xuất hiện với vai trò đầu vào của nhiều nhất một nút.

Mỗi dòng trong q dòng tiếp theo mô tả một truy vấn, gồm hai số nguyên x và k, trong đó x (2≤x≤105) là một mã đầu ra hợp lệ và k (1≤k≤109) là chỉ số của số cần tìm trong dãy đó. Chỉ số trong một dãy bắt đầu từ 1.

Dữ liệu ra

Với mỗi truy vấn x và k, in ra một dòng chứa số thứ k trong dãy của đầu ra có mã x, hoặc none nếu dãy đó không có phần tử với chỉ số này.

Ràng buộc

  • 1≤m≤109, 1≤n≤104, 1≤q≤103.
  • Mạng không có chu trình; mã 1 là đầu vào chung, các mã khác là 2,3,… liên tiếp.
  • 2≤x≤105, x là một mã đầu ra hợp lệ; 1≤k≤109.

Ví dụ

Mạng của ví dụ 2:

flowchart TD IN(["1: 1, 2, ..., 100"]) --> S1["Tách S 1 4 2"] S1 -- "đầu ra 1 (mã 4)" --> M["Gộp M 3 4 6"] S1 -- "đầu ra 2 (mã 2)" --> S2["Tách S 2 3 5"] S2 -- "đầu ra 1 (mã 3)" --> M S2 -- "đầu ra 2 (mã 5)" --> O5(["5"]) M --> O6(["6"])
Input Output Giải thích
200 2 2
S 1 2 3
M 3 2 4
4 99
4 100
100
99
Dãy 2 là 1,3,…,199, dãy 3 là 2,4,…,200. Nút gộp lấy dãy 3 làm đầu vào 1, nên dãy 4 là 2,1,4,3,…,200,199.
100 3 6
S 1 4 2
S 2 3 5
M 3 4 6
6 48
6 49
6 50
6 51
6 52
5 25
47
98
49
51
53
100
Dãy 4 là 1,3,…,99 (50 số), dãy 2 là 2,4,…,100, dãy 3 là 2,6,…,98 (25 số), dãy 5 là 4,8,…,100. Dãy 6 là 2,1,6,3,…,98,49 (50 số đầu), sau đó dãy 3 đã hết nên tiếp theo là 51,53,…,99.
2 3 3
S 1 2 3
S 3 4 5
M 5 2 6
3 1
5 1
6 2
2
none
none
Dãy 3 là 2, dãy 4 là 2, dãy 5 rỗng, dãy 2 là 1, nên dãy 6 chỉ có một số là 1.

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