#P18719. One, Two, Three

    ID: 18055 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-模意义不变量一维前缀和线性 DP离散化树状数组路径恢复链表增量维护

One, Two, Three

One, Two, Three

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,每个元素均为 11、22 或 33。第 ii 个元素还有一个正整数美丽值 bib_i。

你可以任意次(也可以零次)执行如下操作:选择当前序列中连续的一段,如果这一段的元素之和等于 44 或 88,则将整段删除。每次删除后,剩余的左、右两部分立即拼接成一个连续序列。

你需要先使最终剩余元素的数值之和最小;在达到这个最小值的所有方案中,再使剩余元素的美丽值之和最大。

输入格式

第一行一个整数 tt,表示测试用例数,1≤t≤20001\le t\le2000。

每个测试用例包含四行:

  1. 第一行一个整数 nn,1≤n≤3⋅1051\le n\le3\cdot10^5。
  2. 第二行一个长度为 nn、不含空格的字符串 a1a2⋯ana_1a_2\cdots a_n。每个字符为 1、2 或 3,表示原始序列。
  3. 第三行 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n,1≤bi≤991\le b_i\le99。
  4. 第四行一个整数 pp,1≤p≤21\le p\le2,表示此用例的类型。

所有测试用例的 nn 之和不超过 3⋅1053\cdot10^5。

输出格式

对每个测试用例,先输出两个整数:最终剩余元素的最小数值之和,以及在此条件下剩余元素的最大美丽值之和。

如果 p=1p=1,该用例的输出到此结束。

如果 p=2p=2,还要输出达到这两个值的一种操作序列:下一行输出操作次数 kk,之后 kk 行描述各次操作。每行先输出此次删除的元素个数,随后按递增顺序输出这些元素在初始序列中的下标,下标从 11 开始。

每次列出的元素必须在该次操作前的当前序列中连续,并且数值之和为 44 或 88。被删除的元素不能再次使用。kk 可以为 00;此时其后没有操作行。允许输出任意满足要求且达到上述两级最优目标的方案。

原样例

6
3
121
1 2 3
2
3
221
4 5 6
2
3
123
7 8 9
1
6
123221
10 11 12 13 14 15
2
6
312322
15 14 13 12 11 10
2
6
213312
9 8 7 5 5 1
2
0 0
1
3 1 2 3
1 6
1
2 1 2
6 24
3 29
1
4 1 2 3 4
5 25
2
2 5 6
2 1 2
0 0
3
2 2 3
2 4 5
2 1 6

样例第六个用例中,先删除原下标 2,32,3,再删除原下标 4,54,5,此后原下标 1,61,6 在当前序列中相邻,因此最后一步可以删除它们。输出下标始终是原下标,不能改成操作时的位置。