11313: [yosupo] String - Palindromes in Deque
[Creator : ]
Description
There is an initially empty string $s$. Process $Q$ queries.
- `0 $c$`: Add a character $c$ to the beginning of the string $s$.
- `1 $c$`: Add a character $c$ to the end of the string $s$.
- `2`: Remove the character at the beginning of the string $s$.
- `3`: Remove the character at the end of the string $s$.
After processing each query, output the following $3$ parameters in order.
* Number of distinct non-empty palindromic substring of $s$
* Length of the longest palindromic prefix of $s$
* Length of the longest palindromic suffix of $s$
If $s$ is a empty string, output `0 0 0` instead.
- `0 $c$`: Add a character $c$ to the beginning of the string $s$.
- `1 $c$`: Add a character $c$ to the end of the string $s$.
- `2`: Remove the character at the beginning of the string $s$.
- `3`: Remove the character at the end of the string $s$.
After processing each query, output the following $3$ parameters in order.
* Number of distinct non-empty palindromic substring of $s$
* Length of the longest palindromic prefix of $s$
* Length of the longest palindromic suffix of $s$
If $s$ is a empty string, output `0 0 0` instead.
Input
$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
$\vdots$
$\textrm{Query}_{Q - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
$\vdots$
$\textrm{Query}_{Q - 1}$
Constraints
- $1 \leq Q 5\times 10^{5}$
- $c$ is a lowercase English letter.
- The string $s$ is not empty when query $2$ or query $3$ comes.
- $c$ is a lowercase English letter.
- The string $s$ is not empty when query $2$ or query $3$ comes.
Sample 1 Input
9
1 a
1 b
1 c
1 b
1 c
1 b
1 a
3
1 c
Sample 1 Output
1 1 1
2 1 1
3 1 1
4 1 3
5 1 3
6 1 5
7 7 7
6 1 5
7 1 5
Sample 2 Input
12
0 o
0 x
0 o
1 o
1 x
1 o
2
2
2
3
3
3
Sample 2 Output
1 1 1
2 1 1
3 3 3
4 3 2
5 3 4
6 6 6
5 4 3
4 2 3
3 3 3
2 1 1
1 1 1
0 0 0