atcoder#ABC280H. [ABC280Ex] Substring Sort

[ABC280Ex] Substring Sort

配点 : 600600

問題文

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

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

  • MM 個の要素は相異なる。
  • すべての 1iM1 \leq i \leq M に対して、1KiN1 \leq K_i \leq N かつ 1LiRiSKi1 \leq L_i \leq R_i \leq |S_{K_i}| である。
  • すべての 1ijM1 \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] である。

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

辞書順とは 2 つの文字列 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 について、STi 文字目は等しく、Sk 文字目は Tk 文字目よりアルファベット順で真に小さい。

制約

  • 1N1051 \leq N \leq 10^5
  • 1Si1051 \leq \lvert S_i\rvert \leq 10^5
  • $\displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5$
  • 1Q2×1051 \leq Q \leq 2\times 10^5
  • $1 \leq x_1
  • N,Q,x1,x2,,xQN,Q,x_1,x_2,\ldots,x_Q は整数
  • SiS_i は英小文字のみからなる文字列

入力

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

NN

S1S_1

S2S_2

\vdots

SNS_N

QQ

x1x_1 x2x_2 \ldots xQx_Q

出力

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

2
abab
cab
2
5 14
1 3 4
2 1 1

M=16M=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)となります。

なお、55 番目の要素 (1,3,4)(1,3,4) を、44 番目や 66 番目の要素と入れ替えた列も条件をみたすため、 (Kx1,Lx1,Rx1)=(1,1,2),(2,2,3)(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=5M=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}) について、xix_i 番目の要素が (Kxi,Lxi,Rxi)(K_{x_i}, L_{x_i}, R_{x_i}) であるような条件をみたす列は異なる ii の間で共通のものである必要が ない、 すなわち、「任意の 1iQ1\leq i\leq Q について xix_i 番目の要素が (Kxi,Lxi,Rxi)(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