atcoder#ABC280H. [ABC280Ex] Substring Sort

[ABC280Ex] Substring Sort

题目描述

N N 個の文字列 S1,S2,, SN S_1,S_2,\ldots,\ S_N が与えられます。 $ M\ =\ \displaystyle\sum_{i=1}^N\ \frac{|S_i|(|S_i|+1)}{2} $ とおきます。
また、文字列 S S と整数 L, R L,\ R に対し、S[L, R] S[L,\ R] S S L L 文字目から R R 文字目までの文字からなる部分文字列を表します。

整数の三つ組からなる長さ M M の列 $ ((K_1,\ L_1,\ R_1),\ (K_2,\ L_2,\ R_2),\ \ldots,\ (K_M,\ L_M,\ R_M)) $ は以下の条件をみたします:

  • M M 個の要素は相異なる。
  • すべての 1  i  M 1\ \leq\ i\ \leq\ M に対して、1  Ki  N 1\ \leq\ K_i\ \leq\ N かつ 1  Li  Ri  SKi 1\ \leq\ L_i\ \leq\ R_i\ \leq\ |S_{K_i}| である。
  • すべての 1  i  j  M 1\ \leq\ i\ \leq\ j\ \leq\ M に対して、辞書順で SKi[Li, Ri]  SKj[Lj, Rj] S_{K_i}[L_i,\ R_i]\ \leq\ S_{K_j}[L_j,\ R_j] である。

1 1 以上 M M 以下の整数 Q Q x1,x2,, xQ x_1,x_2,\ldots,\ x_Q が与えられます。各 1  i  Q 1\ \leq\ i\ \leq\ Q に対して、(Kxi, Lxi, Rxi) (K_{x_i},\ L_{x_i},\ R_{x_i}) としてあり得るものを 1 1 つずつ求めてください。なお、条件をみたす三つ組の列が必ず 1 1 つ以上存在することが証明できます。条件をみたす三つ組が複数存在する場合、どれを出力しても構いません。また、異なる xi x_i の間で、条件をみたす三つ組の列が共通のものである必要もありません。

辞書順とは 2 2 つの文字列 S, T S,\ T が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で S  T S\ \leq\ T であると言います。 - S  T |S|\ \leq\ |T| かつ S = T[1, S] S\ =\ T[1,\ |S|] である。

  • ある 1 k min(S, T) 1\leq\ k\leq\ \min(|S|,\ |T|) が存在し、1 i k1 1\leq\ i\leq\ k-1 について、S S T T i i 文字目は等しく、S S k k 文字目は T T k k 文字目よりアルファベット順で真に小さい。

输入格式

入力は以下の形式で標準入力から与えられる。

N N S1 S_1 S2 S_2 \vdots SN S_N Q Q x1 x_1 x2 x_2 \ldots xQ x_Q

输出格式

Q Q 行出力せよ。i i 行目には、条件をみたす (Kxi, Lxi, Rxi) (K_{x_i},\ L_{x_i},\ R_{x_i}) としてあり得るものを空白区切りで出力せよ。 条件をみたす三つ組が複数存在する場合、どれを出力してもよい。

2
abab
cab
2
5 14
1 3 4
2 1 1
3
a
a
ba
2
1 2
1 1 1
1 1 1
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

提示

制約

  • 1  N  105 1\ \leq\ N\ \leq\ 10^5
  • 1   Si  105 1\ \leq\ \lvert\ S_i\rvert\ \leq\ 10^5
  • $ \displaystyle\sum_{i=1}^N\ \lvert\ S_i\rvert\leq\ 10^5 $
  • 1  Q  2× 105 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,x1,x2,,xQ N,Q,x_1,x_2,\ldots,x_Q は整数
  • Si S_i は英小文字のみからなる文字列

Sample Explanation 1

M=16 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) $ が考えられます。 この順で並べた時の (Ki,Li, Ri) (K_i,L_i,\ R_i) に対応する SKi[Li, Ri] S_{K_i}[L_i,\ R_i] の列は、(a, a, a, ab, ab, ab, aba, abab, b, b, b, ba, bab, c, ca, cab)となります。 なお、5 5 番目の要素 (1,3,4) (1,3,4) を、4 4 番目や 6 6 番目の要素と入れ替えた列も条件をみたすため、 (Kx1, Lx1, Rx1)=(1,1,2), (2,2,3) (K_{x_1},\ L_{x_1},\ R_{x_1})=(1,1,2),\ (2,2,3) も正解となります。

Sample Explanation 2

M=5 M=5 であり、条件をみたす三つ組の列としては、 (1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2) (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) (2,1,1),\ (3,2,2),\ (1,1,1),\ (3,1,1),\ (3,1,2) が考えられます。 出力する (Kxi, Lxi, Rxi) (K_{x_i},\ L_{x_i},\ R_{x_i}) について、xi x_i 番目の要素が (Kxi, Lxi, Rxi) (K_{x_i},\ L_{x_i},\ R_{x_i}) であるような条件をみたす列は異なる i i の間で共通のものである必要が **ない**、 すなわち、「任意の 1 i Q 1\leq\ i\leq\ Q について xi x_i 番目の要素が (Kxi, Lxi, Rxi) (K_{x_i},\ L_{x_i},\ R_{x_i}) である」 ような列は **必ずしも存在する必要がない** ことに注意してください。