33OJ
登录 注册

#P17809. [ICPC 2019 Nanchang R] Dynamic Suffix Array

[ICPC 2019 Nanchang R] Dynamic Suffix Array

Problem Description

In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used, among others, in full-text indices, data compression algorithms and within the field of bibliometrics.

Assume S[1,n]S[1,n] is a string, let's denote S[i,j]S[i,j] as the substring of SS ranging from ii to jj and denote suffix ii as S[i,n]S[i,n].

The suffix array AA of SS is now defined to be an array of integers providing the starting positions of suffixes of SS in lexicographical order. This means, an entry A[i]A[i] contains the starting position of the ii-th smallest suffix in SS and thus S[A[i−1],n]<S[A[i],n]S[A[i-1],n]<S[A[i],n] always holds for each 1<i≤n1<i\leq n.

Now there is an empty string SS, you need to maintain its suffix array dynamically. There will be qq events of the two kinds below:

  • 1 c : Append a character cc at the end of SS, it is guaranteed that cc is chosen uniformly at random from lower-case english letters aa to zz.
  • 2 k (1≤k≤∣S∣1\leq k\leq |S|): You need to report the position of kk in the current suffix array of SS, which means you need to report the rank of suffix kk.

Please write a program to process these events efficiently.

Input Format

The first line of the input contains an integer qq (2≤q≤10000002 \leq q \leq 1000000), denoting the number of events.

For the next qq lines, each line describes an event. It is guaranteed that the first event is of the first type, and the last event is of the second type.

Output Format

For each event of the second type, output an integer denotes the answer in a single line.

10
1 t
1 s
2 2
1 r
1 w
1 f
1 t
2 2
1 q
2 2
1
3
4