PreVOI 2025 - Contest 3 - Hoán vị
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Gian bếp của Alice có hai dãy bàn song song để đặt các nguyên liệu khi nấu ăn. Có ~n~ loại nguyên liệu và Alice đã đặt trên dãy bàn thứ nhất lần lượt các loại nguyên liệu ~a_1, a_2, \dots, a_n~, trên dãy bàn thứ hai lần lượt các loại nguyên liệu ~b_1, b_2, \dots, b_n~, cả hai dãy đều là hoán vị của ~1, 2, \dots, n~. Khi đứng ở một vị trí nào đó trong gian bếp, Alice có thể lấy được các loại nguyên liệu từ vị trí ~x~ tới vị trí ~y~ ~(1 \le x \le y \le n)~ trên dãy bàn thứ nhất, tức là các loại nguyên ~a_x, \dots, a_y~, và lấy được các nguyên liệu từ vị trí ~u~ đến vị trí ~v~ ~(1 \le u \le v \le n)~ trên dãy bàn thứ hai, tức là các loại nguyên ~b_u, \dots, b_v~. Alice muốn biết có bao nhiêu loại nguyên liệu vừa xuất hiện trong ~a_x, \dots, a_y~ vừa xuất hiện trong ~b_u, \dots, b_v~.
Yêu cầu: Cho hai dãy ~(a_1, a_2, \dots, a_n)~, ~(b_1, b_2, \dots, b_n)~ và ~q~ giả định, giả định thứ ~t~ ~(1 \le t \le q)~ cho biết Alice đứng ở một vị trí nào đó có thể lấy được các loại nguyên liệu từ ~x_t~ đến ~y_t~ trên dãy bàn thứ nhất và có thể lấy được các loại nguyên liệu từ ~u_t~ đến ~v_t~ trên dãy bàn thứ hai, hãy giúp Alice đếm số loại nguyên liệu vừa xuất hiện trong ~a_{x_t}, \dots, a_{y_t}~ vừa xuất hiện trong ~b_{u_t}, \dots, b_{v_t}~.
Input
Dòng đầu tiên chứa hai số nguyên ~n, q~ ~(n, q \le 3 \cdot 10^5)~;
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ là một hoán vị của ~1, 2, \dots, n~;
Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n~ là một hoán vị của ~1, 2, \dots, n~;
Dòng thứ ~t~ ~(1 \le t \le q)~ trong ~q~ dòng tiếp theo chứa bốn số nguyên ~x_t, y_t, u_t, v_t~.
Output
- Gồm ~q~ dòng, dòng thứ ~t~ ~(1 \le t \le q)~ chứa một số nguyên tương ứng câu trả lời cho giả định thứ ~t~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n \le 100~ và ~x_t = u_t, y_t = v_t~ với mọi ~1 \le t \le q~ |
| 2 | ~20\%~ | ~n \le 5000~ |
| 3 | ~30\%~ | ~x_t = u_t~ và ~y_t = v_t~ với mọi ~1 \le t \le q~ |
| 4 | ~30\%~ | Không có giới hạn gì thêm |
Sample Input 1
4 2
1 2 3 4
2 3 4 1
1 3 1 3
1 3 2 4
Sample Output 1
2
1
Bình luận