#1987. 三生三世的财富

三生三世的财富

三生三世的财富

题目描述

标题: 三生三世的财富 - Problem - QOJ.ac

#21426. 三生三世的财富

Statistics

题目背景

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

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

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

题目描述

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

给定长度为 n 的序列 p 和 a,其中 p 是 1…n 的一个排列,ai∈{−2,−1,0,1}。

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

  • 若 ai=0,则该元素被赋值为 0;
  • 若 ai=1,则该元素被赋值为 1;
  • 若 ai=−1,则该元素的值由 Alice 在该时刻决定;
  • 若 ai=−2,则该元素的值由 Bob 在该时刻决定。

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

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

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

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

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

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

输入格式

本题强制在线

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

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

第一行包含两个正整数 n 和 typ。

第二行包含 n 个整数 p1,p2,…,pn。

第三行包含 n 个整数 a1,a2,…,an。

如果 typ=2,第四行包含 n 个整数 A1′,A2′,…,An′。

真正的 Ai 为 Ai′ 与 ansi−1 按位异或后模 2 的结果。

输出格式

对于每一组数据:

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

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

样例

样例输入 #1

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

样例输出 #1

3

样例解释 #1

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

  • 时刻 1:确定第 2 个元素(a2=−2,由 Bob 决定);
  • 时刻 2:确定第 3 个元素(a3=−1,由 Alice 决定);
  • 时刻 3:确定第 1 个元素(a1=−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

样例解释 #2

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

  • 时刻 1:确定第 2 个元素(a2=−1,由 Alice 决定);
  • 时刻 2:确定第 1 个元素(a1=−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≤T≤2×105, 1≤n≤2×105, 1≤typ≤2, 1≤∑n≤2×105。
  • p 是 1…n 的一个排列。
  • ai∈{−2,−1,0,1}。
  • Ai∈{0,1}。

子任务编号 T≤ n≤ typ= ∑n≤ 特殊性质 分值 1 2×105 2×105 1 2×105 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×105 2×105 2×105 B 14 7 2 11 8 1 无 17 9 2 20

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 2

1
2 1
2 1
-1 -1
2