P2824 [HEOI2016/TJOI2016] Sorting

In 2016, sister Jiayuan became fond of number sequences. She often studies various quirky problems about sequences, and now she is working on a hard one that needs your help. The problem is as follows: given a permutation of $1$ to $n$, perform $m$ local sorts on this sequence. There are two types of sorts: - `0 l r` means sorting the numbers in the interval $[l,r]$ in ascending order. - `1 l r` means sorting the numbers in the interval $[l,r]$ in descending order. Note that this sorts the numbers whose **indices** lie in the interval $[l,r]$. Finally, query the number at position $q$.

The first line contains two integers $n$ and $m$, where $n$ is the length of the sequence and $m$ is the number of local sorts. The second line contains $n$ integers, representing a permutation of $1$ to $n$. The next $m$ lines each contain three integers $\text{op}, l, r$, where $\text{op}$ being $0$ means ascending sort, $\text{op}$ being $1$ means descending sort, and $l, r$ specify the interval to sort. Finally, an integer $q$ is given, indicating the position to query after all sorts are finished.

Output a single line containing one integer, the number at position $q$ after performing all local sorts in order.

Hebei NOI Qualifier 2016 Day 1 Problem 2. For $30\%$ of the testdata, $n, m \leq 1000$. For $100\%$ of the testdata, $n, m \leq 10^5$, $1 \leq q \leq n$. Translated by ChatGPT 5