P3541 [POI 2010] Monotonicity

**Translated from POI 2010 Stage 3. Day 0 “[Monotonicity](https://szkopul.edu.pl/problemset/problem/HVVwfLd9uyYNOW6hUZ_Zcnqe/site/?key=statement)”.** For an integer sequence $a_1, a_2, \cdots, a_n$, we define its “monotonic sequence” as a symbol sequence $s_1, s_2, \cdots, s_{n-1}$ consisting of $$, and $=$, where the symbol $s_i$ represents the relation between $a_i$ and $a_{i+1}$. For example, the monotonic sequence of $2, 4, 3, 3, 5, 3$ is $, =, $. For an integer sequence $b_1, b_2, \cdots, b_{n+1}$ and its monotonic sequence $s_1, s_2, \cdots, s_n$, if a symbol sequence $s_1', s_2', \cdots, s_k'$ satisfies that for all $1 \le i \le n$ we have $s_i = s_{((i - 1) \bmod n) + 1}'$, then we say the sequence $s_1, s_2, \cdots, s_n$ “implements” the sequence $s_1', s_2', \cdots, s_k'$. In other words, the sequence $s_1, s_2, \cdots, s_n$ can be obtained by repeating the sequence $s_1', s_2', \cdots, s_k'$ multiple times and then deleting a suffix. For example, the integer sequence $2, 4, 3, 3, 5, 3$ implements at least the following symbol sequences: * $, =$ * $, =, $ * $, =, , $ Given an integer sequence $a_1, a_2, \cdots, a_n$ and a monotonic sequence $s_1, s_2, \cdots, s_k$, find the longest subsequence $a_{i_1}, a_{i_2}, \cdots, a_{i_m}$ $(1 \le i_1 \lt i_2 \lt \cdots \lt i_m \le n)$ such that the monotonic sequence of the subsequence implements the given symbol sequence.

The first line contains two integers $n, k$ separated by spaces, representing the length of the integer sequence $a_i$ and the length of the monotonic sequence $s_j$. The second line contains $n$ integers separated by spaces, representing the sequence $a_i$. The third line contains $k$ symbols separated by spaces, representing the symbol sequence $s_j$.

The first line outputs an integer $m$, representing the length of the longest subsequence of $a_1, a_2, \cdots, a_n$ whose monotonic sequence “implements” the monotonic sequence $s_1, s_2, \cdots, s_n$. The second line outputs any such subsequence $a_{i_1}, a_{i_2}, \cdots, a_{i_n}$, with elements separated by spaces.

For $100\%$ of the testdata, $1 \le n \le 20000$, $1 \le k \le 100$, $1 \le a_i \le 1000000$, $s_j \in \{, =\}$. Translated by ChatGPT 5