Bối cảnh
“Con ngoan, nếu cho con của cải đủ cho ba kiếp ba đời, con có chịu học không?”
Hôm nay, 玛德琳 và 坏德琳 đến trước một cỗ máy kỳ ảo. Trong máy có những quả bóng với bốn màu, mỗi màu có công dụng riêng. Bóng bật màu xanh lam là loại cơ bản nhất; khi bật lên từ nó, bạn nhận được khả năng lướt một lần. Bóng bật màu hồng là phiên bản nâng cấp; khi bật lên từ nó, bạn nhận được hai lần lướt. Bật lên từ bóng trắng không cho bạn lần lướt nào. Bóng vàng sẽ mọc gai sau khi được bật lên một lần, và từ đó bạn không thể chạm vào nó nữa.
Các màn chơi trong đó có thể được mô tả bằng một dãy màu. 玛德琳 và 坏德琳 đã chơi trong đó rất lâu nhưng vẫn chưa vượt qua màn đầu tiên. Vì vậy, 玛德琳 sốt ruột đến phát khóc! Cô quyết định gian lận bằng một công cụ chỉnh sửa! Công cụ này rất đặc biệt: nó chỉ có thể sửa bóng trắng và bóng vàng, và chỉ có thể biến chúng thành bóng xanh lam hoặc bóng hồng; hơn nữa, vị trí của quả bóng được sửa ở mỗi lần đã được xác định sẵn. Khi biết chuyện, 坏德琳 quyết định ngăn 玛德琳 gian lận, nên đã xâm nhập công cụ và giành quyền thay đổi màu của bóng vàng. Đồng thời, 玛德琳 cho rằng một chuỗi bóng giống nhau liên tiếp sẽ khiến màn chơi trở nên dễ hơn. Cô coi độ dễ của một màn chơi là độ dài lớn nhất của các đoạn cùng màu. 玛德琳 muốn tối đa hóa giá trị này, còn 坏德琳 muốn tối thiểu hóa nó.
Mô tả bài toán
Alice và Bob chơi một trò chơi trên một dãy có độ dài $n$. Giá trị của mỗi phần tử trong dãy chỉ có thể là $0$ hoặc $1$, và thời điểm xác định giá trị của mỗi phần tử đã được ấn định trước khi trò chơi bắt đầu.
Cho hai dãy $p$ và $a$ có độ dài $n$, trong đó $p$ là một hoán vị của $1\dots n$, và $a_i\in\{-2,-1,0,1\}$.
Giá trị của phần tử thứ $i$ trong dãy được xác định tại thời điểm thứ $p_i$, theo các quy tắc sau:
- Nếu $a_i=0$, phần tử đó được gán giá trị $0$;
- Nếu $a_i=1$, phần tử đó được gán giá trị $1$;
- Nếu $a_i=-1$, giá trị của phần tử đó do Alice quyết định tại thời điểm ấy;
- Nếu $a_i=-2$, giá trị của phần tử đó do Bob quyết định tại thời điểm ấy.
Trước khi trò chơi bắt đầu, cả Alice và Bob đều biết hai dãy $p$ và $a$. Trò chơi diễn ra trong $n$ thời điểm; tại thời điểm thứ $k$, giá trị tại vị trí $i$ thỏa mãn $p_i=k$ được xác định. Sau $n$ thời điểm, giá trị của mỗi phần tử trong dãy đã được xác định đúng một lần.
Một đoạn liên tiếp cùng màu được định nghĩa là một cặp $(l,r)$ thỏa mãn $l\le r$, sao cho các phần tử từ thứ $l$ đến thứ $r$ đều có cùng giá trị. Nếu không thể mở rộng đoạn đó sang trái hay sang phải (tức là $l=1$ hoặc phần tử thứ $l-1$ có giá trị khác với chúng, đồng thời $r=n$ hoặc phần tử thứ $r+1$ có giá trị khác với chúng), thì nó được gọi là một đoạn liên tiếp cùng màu cực đại. Độ dài của $(l,r)$ là $r-l+1$.
Alice muốn tối đa hóa độ dài lớn nhất trong số tất cả các đoạn liên tiếp cùng màu cực đại của dãy sau thời điểm thứ $n$, còn Bob muốn tối thiểu hóa giá trị đó.
Cho số nguyên dương $typ \in \{1,2\}$.
Nếu $typ=1$, cả hai bên đều hành động theo chiến lược tối ưu. Hãy tìm độ dài lớn nhất trong số các đoạn liên tiếp cùng màu cực đại của dãy cuối cùng. Có thể chứng minh rằng đáp án được xác định duy nhất.
Nếu $typ=2$, bạn được cho thêm một dãy $A$ có độ dài $n$. $A_i \in \{0,1\}$ biểu thị quyết định được thực hiện tại thời điểm thứ $i$ của trò chơi như sau: gọi $x$ là số nguyên dương duy nhất trong $1,2,\dots,n$ thỏa mãn $p_x=i$, rồi gán giá trị $A_i$ cho phần tử thứ $x$ của dãy (có thể xảy ra trường hợp tia vũ trụ đánh trúng vị trí thứ $x$, khiến $a_x,A_i \in \{0,1\}$ nhưng $a_x \neq A_i$). Với mỗi $i=0,1,\dots,n$, hãy tìm $ans_i$, độ dài đoạn liên tiếp cùng màu dài nhất trong dãy cuối cùng nếu mọi quyết định đến hết thời điểm thứ $i$ đều tuân theo dãy $A$, và sau thời điểm thứ $i$ cả hai bên đều hành động theo chiến lược tối ưu.
Dữ liệu vào
Bài toán này bắt buộc xử lý trực tuyến
Dòng đầu tiên chứa một số nguyên dương $T$, là số bộ dữ liệu.
Tiếp theo là $T$ bộ dữ liệu. Trong mỗi bộ dữ liệu:
Dòng đầu tiên chứa hai số nguyên dương $n$ và $typ$.
Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots,p_n$.
Dòng thứ ba chứa $n$ số nguyên $a_1,a_2,\dots,a_n$.
Nếu $typ=2$, dòng thứ tư chứa $n$ số nguyên $A'_1,A'_2,\dots,A'_n$.
Giá trị thực sự của $A_i$ là kết quả lấy XOR theo bit của $A'_i$ và $ans_{i-1}$, rồi lấy phần dư modulo $2$.
Dữ liệu ra
Với mỗi bộ dữ liệu:
Nếu $typ=1$, in ra một số nguyên trên một dòng, là độ dài đoạn liên tiếp cùng màu dài nhất trong dãy cuối cùng khi cả hai bên đều hành động theo chiến lược tối ưu.
Nếu $typ=2$, in ra $n+1$ số nguyên trên một dòng, lần lượt là độ dài đoạn liên tiếp cùng màu dài nhất trong dãy cuối cùng với mỗi $i=0,1,\dots,n$, nếu mọi quyết định đến hết thời điểm thứ $i$ đều tuân theo dãy $A$, và sau thời điểm thứ $i$ cả hai bên đều hành động theo chiến lược tối ưu.
Ví dụ
Dữ liệu vào 1
1 3 1 3 1 2 -1 -2 -1
Dữ liệu ra 1
3
Ghi chú
$p=[3,1,2]$ có nghĩa là $p_1=3,\ p_2=1,\ p_3=2$: phần tử thứ $1$ được xác định tại thời điểm thứ $3$, phần tử thứ $2$ tại thời điểm thứ $1$, và phần tử thứ $3$ tại thời điểm thứ $2$. Vì vậy, thứ tự theo thời gian là:
- Thời điểm $1$: xác định phần tử thứ $2$ ($a_2=-2$, do Bob quyết định);
- Thời điểm $2$: xác định phần tử thứ $3$ ($a_3=-1$, do Alice quyết định);
- Thời điểm $3$: xác định phần tử thứ $1$ ($a_1=-1$, do Alice quyết định).
Alice muốn đoạn cùng màu dài nhất càng dài càng tốt, còn Bob muốn nó càng ngắn càng tốt. Dù Bob đi trước, anh chỉ kiểm soát phần tử thứ $2$ ở chính giữa; Alice kiểm soát hai phần tử ở hai đầu, thứ $1$ và thứ $3$.
Sau khi Bob gán $0$ cho phần tử thứ $2$, Alice có thể gán $0$ cho cả phần tử thứ $1$ và thứ $3$, thu được dãy cuối cùng 0 0 0, với đoạn cùng màu dài nhất có độ dài $3$. Nếu Bob gán $1$ cho phần tử thứ $2$, Alice cũng chọn $1$ cho cả hai phần tử, thu được dãy cuối cùng 1 1 1, và độ dài đoạn cùng màu dài nhất vẫn là $3$.
Hai lựa chọn của Bob dẫn đến kết quả hoàn toàn giống nhau; anh không thể giảm đáp án xuống dưới $3$. Alice cũng chỉ có thể làm cho cả dãy cùng màu là tối đa, nên đáp án là $3$.
Dữ liệu vào 2
1 2 1 2 1 -1 -1
Dữ liệu ra 2
2
Ghi chú
$p=[2,1]$ có nghĩa là $p_1=2,\ p_2=1$: phần tử thứ $1$ được xác định tại thời điểm thứ $2$, và phần tử thứ $2$ tại thời điểm thứ $1$. Giá trị $a$ của cả hai phần tử đều là $-1$, nên cả hai đều do Alice quyết định:
- Thời điểm $1$: xác định phần tử thứ $2$ ($a_2=-1$, do Alice quyết định);
- Thời điểm $2$: xác định phần tử thứ $1$ ($a_1=-1$, do Alice quyết định).
Alice muốn tối đa hóa độ dài đoạn cùng màu dài nhất. Cả hai phần tử đều do cô quyết định, nên cô chỉ cần gán cùng một giá trị cho chúng để thu được 0 0 hoặc 1 1. Khi đó, $(1,2)$ là một đoạn liên tiếp cùng màu cực đại có độ dài $2$. Tổng độ dài của dãy chỉ là $2$, nên đây cũng là kết quả tốt nhất mà cô có thể đạt được.
Dữ liệu vào 3
3 2 1 1 2 -1 -2 4 2 1 3 2 4 -1 0 -2 -1 1 0 0 1 3 1 3 1 2 0 0 1
Dữ liệu ra 3
1 2 2 3 2 2 2
Giới hạn
Bài toán này áp dụng các quan hệ phụ thuộc hợp lý giữa các nhiệm vụ con.
Với mọi bộ dữ liệu, đảm bảo rằng:
$1 \leq T \leq 2 \times 10^5$, $1\le n\le 2\times 10^5$, $1 \le typ \le 2$, $1 \leq \sum n \leq 2 \times 10^5$.
$p$ là một hoán vị của $1\dots n$.
$a_i\in\{-2,-1,0,1\}$.
$A_i\in\{0,1\}$.
| Số hiệu nhiệm vụ con | $T \leq$ | $n \leq$ | $typ=$ | $\sum n \leq$ | Tính chất đặc biệt | Điểm |
|---|---|---|---|---|---|---|
| $1$ | $2 \times 10^5$ | $2 \times 10^5$ | $1$ | $2 \times 10^5$ | A | $3$ |
| $2$ | $40$ | $20$ | $2$ | $40$ | Không có | $9$ |
| $3$ | $200$ | $200$ | $1$ | $200$ | $10$ | |
| $4$ | $2$ | $8$ | ||||
| $5$ | $2000$ | $1000$ | $1$ | $2000$ | $8$ | |
| $6$ | $2 \times 10^5$ | $2 \times 10^5$ | $2 \times 10^5$ | B | $14$ | |
| $7$ | $2$ | $11$ | ||||
| $8$ | $1$ | Không có | $17$ | |||
| $9$ | $2$ | $20$ |
Tính chất đặc biệt A: Đảm bảo $a_i\in\{0,1\}$.
Tính chất đặc biệt B: Đảm bảo rằng $p$ và $a$ được sinh ngẫu nhiên trong số các dãy có độ dài $n$ thỏa mãn các giới hạn.
Chú ý: Các nhiệm vụ con $3,4,5,8,9$ phụ thuộc vào nhiệm vụ con $2$.