题目内容

为了防止大语言模型记忆并泄露输入上下文的敏感数据，安全框架会对输入的长文本进行预扫描，匹配预设的敏感词库（如 $API\_KEY$、身份证号码等）。

一旦在序列中发现了敏感词，系统会在底层的注意力掩码矩阵中对这些“敏感区块”进行动态隔离遮蔽。具体来说，敏感区块内部的词可以互相看到，但外部的任何词都绝对不能看到这些敏感数据。

具体流程如下：

给定一个长度为 $N$ 的主序列 $Token$ 数组 $T$，以及 $K$ 个敏感模式串。

1. 模式匹配与敏感区块合并

i. 在主序列 $T$ 中找出所有敏感模式串的出现位置，得到一组闭区间 $\{[L_1, R_1], [L_2, R_2], \dots, [L_m, R_m]\}$。 ii. 若两个区间 $I_a = [L_a, R_a]$ 和 $I_b = [L_b, R_b]$ 满足相交或首尾相邻条件，则需要进行合并。

• 相交：$I_a \cap I_b \neq \emptyset$
• 首尾相邻：$L_b = R_a + 1$ 或 $L_a = R_b + 1$

2. 动态遮蔽掩码

对于序列中的任意 $Token$ $i$ 和目标 $Token$ $j$（遵循因果律 $j \leq i$），$Token$ $i$ 能否观察到 $Token$ $j$，由以下规则决定： i. 隔离规则：如果 $j$ 属于某个敏感块，那么只有当 $i$ 也身处同一个敏感块内部时，$i$ 才能观察到 $j$。 ii. 正常规则：如果 $j$ 不属于任何敏感块，它对所有满足 $i \geq j$ 的后续 $Token$ 均正常可见。

输入描述

第 $1$ 行: $N$ 和 $K$ 两个整数，以空格分隔，分别为主序列长度和敏感模式串的数量。

第 $2$ 行: $N$ 个整数，以空格分隔，代表主序列的 $Token$ $ID$ 数组。

接下来 $K$ 行：每行首先是一个整数 $M$，代表敏感模式串长度，后面跟着 $M$ 个整数，以空格分隔，代表该敏感模式串的 $Token$ $ID$。

约束条件:

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 100$
• $1 \leq M \leq 1000$

输出描述

$N$ 个整数，以空格分隔，代表每个 $Token$ 整个序列中总共能观察到多少个 $Token$。

样例1

输入

7 2
10 20 30 40 50 60 70
3 20 30 40
2 40 50

输出

1 2 3 4 5 2 3

说明

$1$. 模式匹配与敏感区块合并

• 敏感模式串 $[20, 30, 40]$ 在序列中的索引为 $[1, 3]$
• 敏感模式串 $[40, 50]$ 在序列中的索引为 $[3, 4]$
• 两者可以合并为一个大敏感块，索引为 $[1, 4]$ $2$. 计算可见 $Token$ 数量
• $i=0$ (值 $10$，正常): 可以看到自身。输出: $1$
• $i=1$ (值 $20$，敏感块): 可以看前面正常的，以及当前敏感块里的。输出: $2$
• $i=2$ (值 $30$，敏感块): 可以看前面正常的，以及当前敏感块里的。输出: $3$
• $i=3$ (值 $40$，敏感块): 可以看前面正常的，以及当前敏感块里的。输出: $4$
• $i=4$ (值 $50$，敏感块): 可以看前面正常的，以及当前敏感块里的。输出: $5$
• $i=5$ (值 $60$，正常): 可以看到自身及前面正常的。输出: $2$
• $i=6$ (值 $70$，正常): 可以看到自身及前面正常的。输出: $3$

样例2

输入

9 1
10 20 30 40 50 60 30 40 70
2 30 40

输出

1 2 3 4 3 4 5 6 5

说明

$1$. 模式匹配与敏感区块合并

• 敏感模式串 $[30, 40]$ 在序列中出现了两次：索引 $[2, 3]$ 和 $[6, 7]$
• 它们不相邻，所以形成了两个独立的敏感块。

2. 计算可见Token数量
   • $i=0$ (值 $10$，正常): 可以看到自身。输出: $1$
   • $i=1$ (值 $20$，正常): 可以看到自身及前面正常的。输出: $2$
   • $i=2$ (值 $30$，敏感块 $1$): 可以看前面正常的，以及当前敏感块里的。输出: $3$
   • $i=3$ (值 $40$，敏感块 $1$): 可以看前面正常的，以及当前敏感块里的。输出: $4$
   • $i=4$ (值 $50$，正常): 可以看到自身及前面正常的。输出: $3$
   • $i=5$ (值 $60$，正常): 可以看到自身及前面正常的。输出: $4$
   • $i=6$ (值 $30$，敏感块 $2$): 可以看前面正常的，以及当前敏感块里的。输出: $5$
   • $i=7$ (值 $40$，敏感块 $2$): 可以看前面正常的，以及当前敏感块里的。输出: $6$
   • $i=8$ (值 $70$，正常): 可以看到自身及前面正常的。输出: $5$