Ex - Substring Sort
当前没有测试数据。
Ex - 子字符串排序
得分: $600$ 分
题目描述
给定 $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$ 到 $M$ 之间（包括 $1$ 和 $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$ 个字符。
约束条件
- $1 \leq N \leq 10^5$
- $1 \leq \lvert S_i\rvert \leq 10^5$
- $\displaystyle\sum_{i=1}^N \lvert S_i\rvert\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$ 是由小写英文字母构成的字符串。
输入
从标准输入中按以下格式给出：
输出
输出 $Q$ 行。其中第 $i$ 行应包含满足条件的 $(K_{x_i}, L_{x_i}, R_{x_i})$ 的例子，用空格相隔。 如果有多个满足条件的三元组，任何一个都可输出。
2
abab
cab
2
5 14
1 3 4
2 1 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))$。
对应的三元组 $(K_i,L_i, R_i)$ 按此顺序的 $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)$。
3
a
a
ba
2
1 2
1 1 1
1 1 1
我们有 $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$ 个元素是 $(K_{x_i}, L_{x_i}, R_{x_i})$ 的不一定对于不同的 $i$ 相同； 也就是说，不一定能够找到一个序列，使得对于所有 $1\leq i\leq Q$ 均有 "$x_i$ 个元素是 $(K_{x_i}, L_{x_i}, R_{x_i})$。"
10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489
3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12