1005. 买最小的或最大的

题目描述

有 $N$ 个物品，按照大小从小到大编号为 $1,2,\ldots,N$，其中第 $i$ 个物品的价值为 $C_i$。物品的价值与大小没有关系。

初始时展示集合为空。每轮开始时，你可以将任意多个尚未被购买的物品加入展示集合。物品加入展示集合后，只能在被购买时离开集合，不能主动移除。

每名顾客到来时，展示集合中必须至少有两个物品。顾客的偏好分为两种：

• 偏好为 $0$ 时，顾客购买展示集合中编号最小的物品；
• 偏好为 $1$ 时，顾客购买展示集合中编号最大的物品。

每个物品最多被购买一次。

对于一个二进制字符串 $S$，按照 $S$ 中字符的顺序依次接待 $|S|$ 名顾客。定义 $f(S)$ 为所有合法安排中，被购买物品的价值总和的最大值。

给定一个长度为 $K$ 的二进制字符串 $A$，求

$\sum_{L=1}^{K}\sum_{R=L}^{K}f(A[L,R])$

对 $10^9+7$ 取模后的结果。

其中，$A[L,R]$ 表示字符串 $A_LA_{L+1}\ldots A_R$。计算 $f(A[L,R])$ 时，只接待 $R-L+1$ 名顾客。

输入格式

第一行输入一个整数 $T$，表示测试数据组数。

每组测试数据包含三行：

第一行输入两个整数 $N,K$，分别表示物品数量和字符串长度。

第二行输入 $N$ 个整数 $C_1,C_2,\ldots,C_N$，表示每个物品的价值。

第三行输入一个长度为 $K$ 的二进制字符串 $A$，表示顾客的偏好。

对于一组测试数据：

$2\le N\le 2\times 10^5$；

$1\le K<N$；

$1\le C_i\le 10^9$；

$A_i\in{0,1}$；

$|A|=K$。

OJ 中只有一个正式测试点，该测试点满足：

$T=100$；

$\sum N=3\times 10^6$；

$\sum K=10^6$。

输出格式

对于每组测试数据输出一行，表示所有子串对应的 $f$ 值之和对 $10^9+7$ 取模后的结果。

样例输入

3
2 1
3 10
1
3 2
10 5 4
11
3 2
10 5 4
10

样例输出

10
19
30

来源：2026杭电多校-测试专用（肖岱恩） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1236&pid=1005