ภูมิหลัง
“เด็กดี ถ้ามอบทรัพย์สมบัติให้เจ้าถึงสามชาติสามภพ เจ้าจะเรียนหรือไม่?”
วันนี้ 玛德琳 และ 坏德琳 มาถึงหน้าเครื่องจักรอันน่าอัศจรรย์เครื่องหนึ่ง ภายในเครื่องมีลูกบอลสี่สี ซึ่งแต่ละสีมีประโยชน์ต่างกัน ลูกบอลสีน้ำเงินเป็นลูกบอลแบบพื้นฐานที่สุด เมื่อกระเด้งบนมัน คุณจะได้รับความสามารถในการพุ่งตัวหนึ่งครั้ง ลูกบอลสีชมพูเป็นรุ่นที่เสริมพลังแล้ว เมื่อกระเด้งบนมัน คุณจะพุ่งตัวได้สองครั้ง การกระเด้งบนลูกบอลสีขาวจะไม่ทำให้ได้รับการพุ่งตัว ส่วนลูกบอลสีเหลืองจะมีหนามงอกออกมาหลังจากกระเด้งบนมันหนึ่งครั้ง และหลังจากนั้นคุณจะสัมผัสมันอีกไม่ได้
ด่านต่าง ๆ ภายในเครื่องนี้สามารถอธิบายได้ด้วยลำดับของสี 玛德琳 และ 坏德琳 เล่นอยู่ในนั้นเป็นเวลานาน แต่ก็ยังไม่ผ่านด่านแรก 玛德琳 จึงร้อนใจจนร้องไห้! เธอตัดสินใจใช้โปรแกรมแก้ไขเพื่อโกง! โปรแกรมแก้ไขนี้พิเศษมาก มันแก้ไขได้เฉพาะลูกบอลสีขาวและสีเหลือง และเปลี่ยนให้เป็นได้เฉพาะลูกบอลสีน้ำเงินและสีชมพู อีกทั้งตำแหน่งของลูกบอลที่จะถูกแก้ไขในแต่ละครั้งก็ถูกกำหนดไว้แล้ว เมื่อ 坏德琳 รู้เรื่องนี้ เธอตัดสินใจขัดขวางไม่ให้ 玛德琳 โกง จึงแฮ็กโปรแกรมแก้ไขและได้รับสิทธิ์ในการเปลี่ยนสีลูกบอลสีเหลือง ในขณะเดียวกัน 玛德琳 คิดว่าลูกบอลแบบเดียวกันที่เรียงต่อกันจะทำให้ด่านง่ายขึ้น เธอถือว่าความง่ายของด่านคือความยาวสูงสุดของช่วงที่มีสีเดียวกัน 玛德琳 ต้องการทำให้ค่านี้มากที่สุด ส่วน 坏德琳 ต้องการทำให้ค่านี้น้อยที่สุด
คำอธิบาย
Alice และ Bob เล่นเกมบนลำดับที่มีความยาว $n$ ค่าของสมาชิกแต่ละตัวในลำดับเป็นได้เพียง $0$ หรือ $1$ และเวลาที่จะกำหนดค่าของสมาชิกแต่ละตัวถูกระบุไว้แล้วก่อนเริ่มเกม
กำหนดลำดับ $p$ และ $a$ ที่มีความยาว $n$ โดยที่ $p$ เป็นการเรียงสับเปลี่ยนของ $1\dots n$ และ $a_i\in\{-2,-1,0,1\}$
ค่าของสมาชิกตัวที่ $i$ ในลำดับจะถูกกำหนด ณ เวลา $p_i$ ตามกฎต่อไปนี้:
- ถ้า $a_i=0$ สมาชิกตัวนี้จะได้รับค่า $0$;
- ถ้า $a_i=1$ สมาชิกตัวนี้จะได้รับค่า $1$;
- ถ้า $a_i=-1$ Alice จะเป็นผู้กำหนดค่าของสมาชิกตัวนี้ ณ เวลานั้น;
- ถ้า $a_i=-2$ Bob จะเป็นผู้กำหนดค่าของสมาชิกตัวนี้ ณ เวลานั้น
ก่อนเริ่มเกม ทั้ง Alice และ Bob รู้ลำดับ $p$ และลำดับ $a$ เกมดำเนินไปทั้งหมด $n$ ช่วงเวลา ณ เวลา $k$ จะกำหนดค่าที่ตำแหน่ง $i$ ซึ่งสอดคล้องกับ $p_i=k$ หลังจากครบ $n$ ช่วงเวลา สมาชิกทุกตัวในลำดับจะถูกกำหนดค่าตัวละหนึ่งครั้งพอดี
ช่วงต่อเนื่องสีเดียวกันนิยามว่าเป็นคู่อันดับ $(l,r)$ ที่สอดคล้องกับ $l\le r$ และสมาชิกตั้งแต่ตัวที่ $l$ ถึงตัวที่ $r$ มีค่าเท่ากันทั้งหมด หากช่วงนี้ไม่สามารถขยายออกไปทางซ้ายหรือขวาได้อีก (นั่นคือ $l=1$ หรือสมาชิกตัวที่ $l-1$ มีค่าต่างจากสมาชิกเหล่านั้น และ $r=n$ หรือสมาชิกตัวที่ $r+1$ มีค่าต่างจากสมาชิกเหล่านั้น) จะเรียกช่วงนี้ว่าช่วงต่อเนื่องสีเดียวกันที่ขยายต่อไม่ได้ ความยาวของ $(l,r)$ คือ $r-l+1$
Alice ต้องการทำให้ความยาวสูงสุดในบรรดาช่วงต่อเนื่องสีเดียวกันที่ขยายต่อไม่ได้ทั้งหมดของลำดับหลังเวลา $n$ มีค่ามากที่สุด ส่วน Bob ต้องการทำให้ค่านี้น้อยที่สุด
กำหนดจำนวนเต็มบวก $typ \in \{1,2\}$
ถ้า $typ=1$ ทั้งสองฝ่ายจะเล่นตามกลยุทธ์ที่ดีที่สุด จงหาความยาวสูงสุดของช่วงต่อเนื่องสีเดียวกันที่ขยายต่อไม่ได้ในลำดับสุดท้าย สามารถพิสูจน์ได้ว่าคำตอบมีค่าแน่นอน
ถ้า $typ=2$ จะมีลำดับ $A$ ที่มีความยาว $n$ เพิ่มเติมให้ โดย $A_i \in \{0,1\}$ แสดงถึงการตัดสินใจ ณ เวลา $i$ ของเกมดังนี้: ให้ $x$ เป็นจำนวนเต็มบวกเพียงตัวเดียวใน $1,2,\dots,n$ ที่สอดคล้องกับ $p_x=i$ แล้วกำหนดค่าสมาชิกตัวที่ $x$ ในลำดับเป็น $A_i$ (อาจเกิดกรณีที่รังสีคอสมิกชนตำแหน่ง $x$ ทำให้ $a_x,A_i \in \{0,1\}$ แต่ $a_x \neq A_i$) สำหรับแต่ละ $i=0,1,\dots,n$ จงหาความยาว $ans_i$ ของช่วงต่อเนื่องสีเดียวกันที่ยาวที่สุดในลำดับสุดท้าย หากเล่นตามการตัดสินใจของลำดับ $A$ จนถึงและรวมเวลา $i$ และหลังจากเวลา $i$ สิ้นสุดลง ทั้งสองฝ่ายเล่นตามกลยุทธ์ที่ดีที่สุด
ข้อมูลนำเข้า
ข้อนี้บังคับให้ประมวลผลแบบออนไลน์
บรรทัดแรกมีจำนวนเต็มบวก $T$ ซึ่งแทนจำนวนชุดทดสอบ
จากนั้นมีชุดทดสอบทั้งหมด $T$ ชุด โดยในแต่ละชุด:
บรรทัดแรกมีจำนวนเต็มบวกสองจำนวน $n$ และ $typ$
บรรทัดที่สองมีจำนวนเต็ม $n$ จำนวน $p_1,p_2,\dots,p_n$
บรรทัดที่สามมีจำนวนเต็ม $n$ จำนวน $a_1,a_2,\dots,a_n$
ถ้า $typ=2$ บรรทัดที่สี่จะมีจำนวนเต็ม $n$ จำนวน $A'_1,A'_2,\dots,A'_n$
ค่า $A_i$ ที่แท้จริงคือผลลัพธ์จากการทำ XOR ระดับบิตระหว่าง $A'_i$ กับ $ans_{i-1}$ แล้วนำมาหาเศษเมื่อหารด้วย $2$
ข้อมูลส่งออก
สำหรับแต่ละชุดทดสอบ:
ถ้า $typ=1$ ให้พิมพ์จำนวนเต็มหนึ่งจำนวนในหนึ่งบรรทัด แทนความยาวของช่วงต่อเนื่องสีเดียวกันที่ยาวที่สุดในลำดับสุดท้ายเมื่อทั้งสองฝ่ายเล่นตามกลยุทธ์ที่ดีที่สุด
ถ้า $typ=2$ ให้พิมพ์จำนวนเต็ม $n+1$ จำนวนในหนึ่งบรรทัด โดยสำหรับแต่ละ $i=0,1,\dots,n$ จำนวนเหล่านี้แทนความยาวของช่วงต่อเนื่องสีเดียวกันที่ยาวที่สุดในลำดับสุดท้าย หากเล่นตามการตัดสินใจของลำดับ $A$ จนถึงและรวมเวลา $i$ และหลังจากเวลา $i$ สิ้นสุดลง ทั้งสองฝ่ายเล่นตามกลยุทธ์ที่ดีที่สุด
ตัวอย่าง
ข้อมูลนำเข้า 1
1 3 1 3 1 2 -1 -2 -1
ข้อมูลส่งออก 1
3
หมายเหตุ
$p=[3,1,2]$ หมายความว่า $p_1=3,\ p_2=1,\ p_3=2$: สมาชิกตัวที่ $1$ ถูกกำหนดค่า ณ เวลา $3$ สมาชิกตัวที่ $2$ ถูกกำหนดค่า ณ เวลา $1$ และสมาชิกตัวที่ $3$ ถูกกำหนดค่า ณ เวลา $2$ ดังนั้นลำดับเวลาจึงเป็นดังนี้:
- เวลา $1$: กำหนดค่าสมาชิกตัวที่ $2$ ($a_2=-2$ จึงกำหนดโดย Bob);
- เวลา $2$: กำหนดค่าสมาชิกตัวที่ $3$ ($a_3=-1$ จึงกำหนดโดย Alice);
- เวลา $3$: กำหนดค่าสมาชิกตัวที่ $1$ ($a_1=-1$ จึงกำหนดโดย Alice)
Alice ต้องการให้ช่วงสีเดียวกันที่ยาวที่สุดยาวเท่าที่จะเป็นไปได้ ส่วน Bob ต้องการให้สั้นเท่าที่จะเป็นไปได้ แม้ Bob จะเล่นก่อน แต่เขาควบคุมได้เพียงสมาชิกตัวที่ $2$ ซึ่งอยู่ตรงกลาง ส่วน Alice ควบคุมสมาชิกตัวที่ $1$ และ $3$ ซึ่งอยู่ที่ปลายทั้งสอง
หลังจาก Bob กำหนดค่าสมาชิกตัวที่ $2$ เป็น $0$ แล้ว Alice สามารถกำหนดค่าสมาชิกตัวที่ $1$ และ $3$ เป็น $0$ เช่นกัน ได้ลำดับสุดท้ายเป็น 0 0 0 ซึ่งมีช่วงสีเดียวกันที่ยาวที่สุดยาว $3$ หาก Bob กำหนดค่าสมาชิกตัวที่ $2$ เป็น $1$ Alice ก็เลือก $1$ ทั้งคู่เช่นกัน ได้ลำดับสุดท้ายเป็น 1 1 1 และความยาวของช่วงสีเดียวกันที่ยาวที่สุดยังคงเป็น $3$
ทางเลือกทั้งสองของ Bob ให้ผลเหมือนกันทุกประการ เขาไม่สามารถลดคำตอบให้ต่ำกว่า $3$ ได้ และ Alice ก็ทำได้มากที่สุดเพียงทำให้ทั้งลำดับมีสีเดียวกัน ดังนั้นคำตอบคือ $3$
ข้อมูลนำเข้า 2
1 2 1 2 1 -1 -1
ข้อมูลส่งออก 2
2
หมายเหตุ
$p=[2,1]$ หมายความว่า $p_1=2,\ p_2=1$: สมาชิกตัวที่ $1$ ถูกกำหนดค่า ณ เวลา $2$ และสมาชิกตัวที่ $2$ ถูกกำหนดค่า ณ เวลา $1$ ค่า $a$ ของสมาชิกทั้งสองเป็น $-1$ จึงกำหนดโดย Alice ทั้งคู่:
- เวลา $1$: กำหนดค่าสมาชิกตัวที่ $2$ ($a_2=-1$ จึงกำหนดโดย Alice);
- เวลา $2$: กำหนดค่าสมาชิกตัวที่ $1$ ($a_1=-1$ จึงกำหนดโดย Alice)
Alice ต้องการทำให้ความยาวมากที่สุดสำหรับช่วงสีเดียวกันที่ยาวที่สุด เธอเป็นผู้กำหนดค่าของสมาชิกทั้งสอง เพียงกำหนดให้ทั้งคู่มีค่าเท่ากัน ก็จะได้ 0 0 หรือ 1 1 ซึ่ง $(1,2)$ เป็นช่วงต่อเนื่องสีเดียวกันที่ขยายต่อไม่ได้และมีความยาว $2$ และเนื่องจากทั้งลำดับยาวเพียง $2$ นี่จึงเป็นผลลัพธ์ที่ดีที่สุดที่เธอทำได้
ข้อมูลนำเข้า 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
ข้อมูลส่งออก 3
1 2 2 3 2 2 2
ข้อจำกัด
ข้อนี้เปิดใช้การขึ้นต่อกันของงานย่อยอย่างเหมาะสม
สำหรับข้อมูลทั้งหมด รับประกันว่า:
$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$ เป็นการเรียงสับเปลี่ยนของ $1\dots n$
$a_i\in\{-2,-1,0,1\}$
$A_i\in\{0,1\}$
| หมายเลขงานย่อย | $T \leq$ | $n \leq$ | $typ=$ | $\sum n \leq$ | คุณสมบัติพิเศษ | คะแนน |
|---|---|---|---|---|---|---|
| $1$ | $2 \times 10^5$ | $2 \times 10^5$ | $1$ | $2 \times 10^5$ | A | $3$ |
| $2$ | $40$ | $20$ | $2$ | $40$ | ไม่มี | $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$ | ไม่มี | $17$ | |||
| $9$ | $2$ | $20$ |
คุณสมบัติพิเศษ A: รับประกันว่า $a_i\in\{0,1\}$
คุณสมบัติพิเศษ B: รับประกันว่า $p$ และ $a$ ถูกสุ่มสร้างจากลำดับที่มีความยาว $n$ และเป็นไปตามข้อจำกัด
หมายเหตุ: งานย่อย $3,4,5,8,9$ ขึ้นต่อกับงานย่อย $2$