AT_abc280_h [ABC280Ex] Substring Sort

题目描述

给定 $N$ 个字符串 $S_1,S_2,\ldots,S_N$。令 $M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$。

对于字符串 $S$ 和整数 $L, R$，$S[L, R]$ 表示 $S$ 的第 $L$ 个字符到第 $R$ 个字符组成的子串。

长度为 $M$ 的三元组序列 $((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M))$ 满足以下条件：

• $M$ 个元素互不相同。
• 对于所有 $1 \leq i \leq M$，有 $1 \leq K_i \leq N$ 且 $1 \leq L_i \leq R_i \leq |S_{K_i}|$。
• 对于所有 $1 \leq i \leq j \leq M$，有 $S_{K_i}[L_i, R_i] \leq S_{K_j}[L_j, R_j]$（按字典序比较）。

给定 $Q$ 个整数 $x_1, x_2, \ldots, x_Q$，其中 $1 \leq x_1 < x_2 < \cdots < x_Q \leq M$。对于每个 $1 \leq i \leq Q$，请各自求出一个可能的 $(K_{x_i}, L_{x_i}, R_{x_i})$。可以证明，满足条件的三元组序列至少存在一个。如果存在多个满足条件的三元组，输出任意一个即可。不同 $x_i$ 之间，不要求三元组序列相同。

字典序的定义如下：对于两个字符串 $S, T$，当且仅当满足以下任一条件时，$S \leq T$（按字典序）：

• $|S| \leq |T|$ 且 $S = T[1, |S|]$。
• 存在 $1 \leq k \leq \min(|S|, |T|)$，对于所有 $1 \leq i \leq k-1$，$S$ 和 $T$ 的第 $i$ 个字符相等，且 $S$ 的第 $k$ 个字符在字母表中严格小于 $T$ 的第 $k$ 个字符。

输入格式

输入按以下格式从标准输入给出。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$
$Q$
$x_1$ $x_2$ $\ldots$ $x_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出一个满足条件的 $(K_{x_i}, L_{x_i}, R_{x_i})$，用空格分隔。若存在多个满足条件的三元组，输出任意一个即可。

输入输出样例 #1

输入 #1

2
abab
cab
2
5 14

输出 #1

1 3 4
2 1 1

输入输出样例 #2

输入 #2

3
a
a
ba
2
1 2

输出 #2

1 1 1
1 1 1

输入输出样例 #3

输入 #3

10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489

输出 #3

3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12

说明/提示

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq |S_i| \leq 10^5$
• $\displaystyle\sum_{i=1}^N |S_i| \leq 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq x_1 < x_2 < \cdots < x_Q \leq \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$
• $N, Q, x_1, x_2, \ldots, x_Q$ 均为整数
• $S_i$ 仅由小写英文字母组成

样例解释 1

$M=16$，满足条件的三元组序列可以为：$(1,1,1), (1,3,3), (2,2,2), (1,1,2), (1,3,4), (2,2,3), (1,1,3), (1,1,4), (1,2,2), (1,4,4), (2,3,3), (1,2,3), (1,2,4), (2,1,1), (2,1,2), (2,1,3)$。按此顺序排列时，对应的 $S_{K_i}[L_i, R_i]$ 为（a, a, a, ab, ab, ab, aba, abab, b, b, b, ba, bab, c, ca, cab）。注意，第 $5$ 个元素 $(1,3,4)$ 与第 $4$ 个或第 $6$ 个元素互换也满足条件，因此 $(K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3)$ 也是正确答案。

样例解释 2

$M=5$，满足条件的三元组序列可以为：$(1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2)$ 或 $(2,1,1), (3,2,2), (1,1,1), (3,1,1), (3,1,2)$。对于输出的 $(K_{x_i}, L_{x_i}, R_{x_i})$，不要求所有 $x_i$ 对应的三元组来自同一个满足条件的序列。

由 ChatGPT 4.1 翻译