{"code":"2023janplatinum1","name":"USACO 2023 January Contest, Platinum, Tractor Paths","description":"**Note: Giới hạn thời gian cho bài này là 4 giây và giới hạn bộ nhớ là 512MB.**\r\n\r\nNông dân John có $N$ $(2 \\le N \\le 2 \\times 10^5)$ chiếc máy kéo, trong đó máy kéo thứ $i$ chỉ có thể sử dụng trong khoảng thời gian $[l_i, r_i]$. Các khoảng thời gian của máy kéo có điểm đầu trái $l_1 < l_2 < ... < l_n$ và điểm cuối phải $r_1 \\le r_2 \\le ... \\le r_n$. Một số máy kéo là đặc biệt.\r\n\r\nHai máy kéo $i$ và $j$ được gọi là kề nhau nếu $[l_i, r_i]$ và $[l_j, r_j]$ giao nhau. Nông dân John có thể chuyển từ một máy kéo sang bất kỳ máy kéo kề nhau nào. Một đường đi giữa hai máy kéo $a$ và $b$ bao gồm một chuỗi các lần chuyển, sao cho máy kéo đầu tiên trong chuỗi là $a$, máy kéo cuối cùng là $b$, và hai máy kéo liên tiếp trong chuỗi là kề nhau. Người ta đảm bảo rằng luôn có một đường đi giữa máy kéo $1$ và máy kéo $N$. Độ dài của một con đường là số lần chuyển (hoặc tương đương, số máy kéo trong đó trừ đi $1$).\r\n\r\nBạn được cho $Q$ $(1 \\le Q \\le 2 \\times 10^5)$ truy vấn, mỗi truy vấn chỉ định một cặp máy kéo $a$ và $b$ $(1 \\le a < b \\le N)$. Đối với mỗi truy vấn, hãy xuất ra hai số nguyên:\r\n- Độ dài của đường đi ngắn nhất giữa máy kéo $a$ và máy kéo $b$.\r\n- Số lượng máy kéo đặc biệt sao cho tồn tại ít nhất một đường đi ngắn nhất từ máy kéo $a$ đến máy kéo $b$ đi qua máy kéo đó.\r\n\r\n#### Input\r\n- Dòng đầu tiên là số $N$ và $Q$\r\n- Dòng thứ hai là xâu kí tự có độ dài $2N$ chỉ bao gồm kí tự $'L'$ và $'R'$, biểu diễn cho thời điểm bắt đầu và kết thúc được xếp theo thứ tự. Với mọi tiền tố của xâu số lượng kí tự $'R'$ không vượt quá số lượng kí tự $'L'$, số lượng hai kí tự xuất hiện trong xâu bằng nhau. Vị trí của kí tự $'L'$ thứ $i$ là biểu diễn cho thời gian máy thứ $i$ có thể sử dụng, và vị trí của kí tự $'R'$ thứ $i$ là biểu diễn cho thời gian máy thứ $i$ không được sử dụng nữa.\r\n- Dòng tiếp theo là xâu nhị phân đồ dài $N$ thể hiện các máy kéo đặc biệt, $s_i = 1$ nếu máy kéo thứ $i$ là đặc biệt, và ngược lại.\r\n- $Q$ dòng tiếp theo gồm $2$ số $a$ và $b$ thể hiện các truy vấn.\r\n\r\n#### Output\r\n- Gồm $Q$ dòng, mỗi dòng là $2$ số là đáp án của các truy vấn in theo thứ tự trong đề bài.\r\n\r\n#### Scoring\r\n- Subtask $1$: $N, Q \\le 5000$.\r\n- Subtask $2$: Có tối đa $10$ máy kéo đặc biệt.\r\n- Subtask $3$: Không có ràng buộc gì thêm\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        8 10\r\n        LLLLRLLLLRRRRRRR\r\n        11011010\r\n        1 2\r\n        1 3\r\n        1 4\r\n        1 5\r\n        1 6\r\n        1 7\r\n        1 8\r\n        2 3\r\n        2 4\r\n        2 5\r\n        ```\r\n\r\n    ???+ \"Output\"\r\n        ```\r\n        1 2\r\n        1 1\r\n        1 2\r\n        2 4\r\n        2 3\r\n        2 4\r\n        2 3\r\n        1 1\r\n        1 2\r\n        1 2\r\n        ```\r\n    ??? warning \"Note\"\r\n        Có $8$ máy kéo theo thứ tự như sau:  $[1, 5], [2, 10], [3, 11], [4, 12], [6, 13], [7, 14], [8, 15], [9, 16]$.\r\n        Trong truy vấn thứ $4$, có $3$ đường đi ngắn nhất giữa máy kéo $1$ và máy kéo $5$. $1 \\rightarrow 2 \\rightarrow 5$, $1 \\rightarrow 3 \\rightarrow 5$, và $1 \\rightarrow 4 \\rightarrow 5$. Độ dài của các đường đi này là $2$.\r\n        Thêm nữa, mỗi máy kéo $1, 2, 3, 4, 5$ là đều xuất hiện ít nhất một lần trong các đường đi trên, do vậy có tất cả $4$ máy kéo đặc biệt xuất hiện là $1, 2, 4, 5$.","points":1000.0,"partial":true,"time_limit":4.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}