#P18752. [2027年国家集训队互测] Wealth Across Three Lifetimes

    ID: 18088 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTS笛卡尔树单调栈树形 DP消除被支配候选动态 DPSplay

[2027年国家集训队互测] Wealth Across Three Lifetimes

Wealth Across Three Lifetimes

题目背景

“好孩子,假如给你三生三世的财富,学否?”

今天,玛德琳和坏德琳来到了一个梦幻的机器面前。机器里面有四种颜色的球,各有各的用处。蓝色弹球是最基础的弹球,你弹上去会获得一次冲刺能力。粉色弹球是加强版,你弹上去会获得两次冲刺。白色弹球弹上去不能获得冲刺。黄色弹球弹了一次之后会长出刺,并且以后你不能在接触它。

这里面的关卡可以通过一个颜色序列来描述。玛德琳和坏德琳在里面玩了很久,但还没通过第一关。于是玛德琳急哭了!她决定通过修改器作弊!这个修改器很特别,只能修改白弹球和黄弹球,且只能修改成蓝弹球和粉弹球,而且每一次被修改的弹球位置是确定的。而坏德琳得知了此事,她决定阻止玛德琳作弊,所以黑了这个修改器,获得了修改黄弹球颜色的权限。同时,玛德琳认为,一连串相同的弹球会让关卡变得简单。她认为一个关卡的简单度是同色段长度的最大值。玛德琳想要最大化这个值,而坏德琳想要最小化这个值。

题目描述

Alice 和 Bob 在一个长度为 nn 的序列上博弈。序列中每个元素的值只能是 00 或 11,且每个元素的取值时刻在游戏开始前就已确定。

给定长度为 nn 的序列 pp 和 aa,其中 pp 是 1…n1\dots n 的一个排列,ai∈{−2,−1,0,1}a_i\in\{-2,-1,0,1\}。

序列的第 ii 个元素会在第 pip_i 个时刻确定取值,规则如下:

  • 若 ai=0a_i=0,则该元素被赋值为 00;

  • 若 ai=1a_i=1,则该元素被赋值为 11;

  • 若 ai=−1a_i=-1,则该元素的值由 Alice 在该时刻决定;

  • 若 ai=−2a_i=-2,则该元素的值由 Bob 在该时刻决定。

游戏开始前,Alice 和 Bob 都知道序列 pp 和序列 aa。游戏共进行 nn 个时刻,第 kk 个时刻确定的是满足 pi=kp_i=k 的那个位置 ii 的取值;nn 个时刻结束后,序列的每个元素都恰好被确定了一次取值。

同色连续段被定义为一个二元组 (l,r)(l,r) 满足 l≤rl\le r,且第 ll 个元素到第 rr 个元素的值全部相同;若它不能再向左右延伸(即 l=1l=1 或第 l−1l-1 个元素与它们不同,且 r=nr=n 或第 r+1r+1 个元素与它们不同),则称它是一个极长同色连续段。(l,r)(l,r) 的长度为 r−l+1r-l+1。

Alice 希望最大化第 nn 个时刻后序列所有极长同色连续段长度的最大值,Bob 希望最小化该值。

给定正整数 typ∈{1,2}typ \in \{1,2\}。

如果 typ=1typ=1,双方都会按最优策略行动,请求出最终序列极长同色连续段长度的最大值。可以证明答案是确定的。

如果 typ=2typ=2,额外给出长度为 nn 的序列 AA。Ai∈{0,1}A_i \in \{0,1\},表示博弈的第 ii 个时刻发生的决策为:令 xx 为唯一满足 px=ip_x=i 的 1,2,…,n1,2,\dots,n 中的正整数,将序列的第 xx 个元素赋值为 AiA_i (可能发生宇宙射线击中了第 xx 个位置导致 ax,Ai∈{0,1}a_x,A_i \in \{0,1\} 且 ax≠Aia_x \neq A_i 的情况)。请求出对于 i=0,1,…,ni=0,1,\dots,n,如果第 ii 个时刻及之前都按照 AA 序列的决策博弈,第 ii 个时刻结束后双方都按最优策略行动,最终序列中最长同色连续段的长度 ansians_i。

输入格式

本题强制在线

第一行包含一个正整数 TT,表示数据组数。

接下来一共 TT 组数据,在每组数据中:

第一行包含两个正整数 nn 和 typtyp。

第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\dots,p_n。

第三行包含 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

如果 typ=2typ=2,第四行包含 nn 个整数 A1′,A2′,…,An′A'_1,A'_2,\dots,A'_n。

真正的 AiA_i 为 Ai′A'_i 与 ansi−1ans_{i-1} 按位异或后模 22 的结果。

输出格式

对于每一组数据:

如果 typ=1typ=1 输出一行一个整数,表示双方都按最优策略行动时,最终序列中最长同色连续段的长度。

如果 typ=2typ=2 输出一行 n+1n+1 个整数,表示对于 i=0,1,…,ni=0,1,\dots,n,如果第 ii 个时刻及之前都按照 AA 序列的决策博弈,第 ii 个时刻结束后双方都按最优策略行动,最终序列中最长同色连续段的长度。

样例

样例输入 #1

1
3 1
3 1 2
-1 -2 -1

样例输出 #1

3

样例解释 #1

p=[3,1,2]p=[3,1,2] 表示 p1=3, p2=1, p3=2p_1=3,\ p_2=1,\ p_3=2:第 11 个元素在第 33 个时刻确定,第 22 个元素在第 11 个时刻确定,第 33 个元素在第 22 个时刻确定。于是时刻顺序为:

  • 时刻 11:确定第 22 个元素(a2=−2a_2=-2,由 Bob 决定);

  • 时刻 22:确定第 33 个元素(a3=−1a_3=-1,由 Alice 决定);

  • 时刻 33:确定第 11 个元素(a1=−1a_1=-1,由 Alice 决定)。

Alice 想要最长同色段尽可能长,Bob 想要尽可能短。Bob 虽然先手,但只掌控正中间的第 22 个元素;Alice 掌控第 11、33 两个端点元素。

Bob 把第 22 个元素定为 00 后,Alice 可以把第 11、33 个元素也都定为 00,最终序列为 0 0 0,最长同色段长度为 33;Bob 若把第 22 个元素定为 11,Alice 同样都取 11,最终序列为 1 1 1,最长同色段长度仍为 33。

Bob 的两种选法导致的结果完全相同,他无法把答案压到 33 以下;而 Alice 也至多让整个序列同色,故答案为 33。

样例输入 #2

1
2 1
2 1
-1 -1

样例输出 #2

2

样例解释 #2

p=[2,1]p=[2,1] 表示 p1=2, p2=1p_1=2,\ p_2=1:第 11 个元素在第 22 个时刻确定,第 22 个元素在第 11 个时刻确定。两个元素的 aa 值都是 −1-1,故都由 Alice 决定:

  • 时刻 11:确定第 22 个元素(a2=−1a_2=-1,由 Alice 决定);

  • 时刻 22:确定第 11 个元素(a1=−1a_1=-1,由 Alice 决定)。

Alice 想要最大化最长同色段。两个元素都由她决定,她只要给两者赋相同的值,就得到 0 0 或 1 1,此时 (1,2)(1,2) 是长度为 22 的极长同色连续段;而序列总长度只有 22,故这也是她能取得的最好结果。

样例输入 #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≤T≤2×1051 \leq T \leq 2 \times 10^5, 1≤n≤2×1051\le n\le 2\times 10^5, 1≤typ≤21 \le typ \le 2, 1≤∑n≤2×1051 \leq \sum n \leq 2 \times 10^5。

  • pp 是 1…n1\dots n 的一个排列。

  • ai∈{−2,−1,0,1}a_i\in\{-2,-1,0,1\}。

  • Ai∈{0,1}A_i\in\{0,1\}。

子任务编号 T≤T \leq n≤n \leq typ=typ= ∑n≤\sum n \leq 特殊性质 分值
11 2×1052 \times 10^5 11 2×1052 \times 10^5 A 33
22 4040 2020 22 4040 无 99
33 200200 11 200200 1010
44 22 88
55 20002000 10001000 11 20002000
66 2×1052 \times 10^5 2×1052 \times 10^5 B 1414
77 22 1111
88 11 无 1717
99 22 2020

特殊性质 A: 保证 ai∈{0,1}a_i\in\{0,1\}。

特殊性质 B: 保证 pp 和 aa 在长度为 nn 且符合限制的序列中随机生成。

注意:子任务 22 被子任务 3,4,5,8,93,4,5,8,9 依赖。

子任务表