#456 Array Rotation and Queries

Statement

다다스는 다음 쿼리를 한 번당 $O(1)$ 에 처리하는 코드를 작성했다. 여러분도 해 보자.

현재 수열을 $A=[A_1,A_2,\cdots,A_N]$ 이라 하자. 수열에 값 $x$ 가 존재할 때, $A_{\operatorname{idx}(x)}=x$ 를 만족하는 유일한 위치를 $\operatorname{idx}(x)$ 라 정의한다.

두 정수 $x,y$ 가 주어지는 쿼리는 다음과 같이 처리한다.

현재 수열에 $x$ 와 $y$ 가 모두 존재하며, $\operatorname{idx}(x)\leq \operatorname{idx}(y)$ 임이 보장된다.
구간 $[\operatorname{idx}(x),\operatorname{idx}(y)]$ 의 원소에 각각 $-1$ 을 곱한 뒤, 이 구간의 순서를 뒤집는다.

즉, 쿼리 직전의 해당 구간이

[x,\ A_{\operatorname{idx}(x)+1},\ \cdots,\ A_{\operatorname{idx}(y)-1},\ y]

였다면, 쿼리 직후에는

[-y,\ -A_{\operatorname{idx}(y)-1},\ \cdots,\ -A_{\operatorname{idx}(x)+1},\ -x]

가 된다.

초기 수열은 $[1,2,\cdots,N]$ 이다. $Q$ 개의 쿼리를 모두 처리한 뒤의 수열을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ case $_1$ case $_2$ $\vdots$ case $_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ Q$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_Q\ y_Q$

$i$ 번 쿼리는 두 정수 $x_i,y_i$ 로 주어진다. 각 쿼리는 그 직전의 현재 수열에 대해 문제의 보장 조건을 만족한다.

각 테스트 케이스마다, 모든 쿼리를 처리한 뒤의 수열을 한 줄에 출력한다. 수열의 원소는 공백으로 구분한다.

$1\leq T\leq 20$ .
$1\leq N\leq 200\,000$ .
$1\leq Q\leq 5\,000\,000$ .
$-N\leq x_i,y_i\leq N$ ( $1\leq i\leq Q$ ).
$x_i\neq 0$ 이고 $y_i\neq 0$ 이다 ( $1\leq i\leq Q$ ).
$i$ 번 쿼리 직전에 현재 수열에 $x_i,y_i$ 가 모두 존재하며, $\operatorname{idx}(x_i)\leq \operatorname{idx}(y_i)$ 이다 ( $1\leq i\leq Q$ ).
모든 테스트 케이스에 대한 $N$ 의 합은 $200\,000$ 이하이다.
모든 테스트 케이스에 대한 $Q$ 의 합은 $5\,000\,000$ 이하이다.

#	Score	Constraints
1	9	$N=1$ .
2	18	모든 테스트 케이스에 대한 $N$ 의 합은 $2\,000$ 이하이다. 모든 테스트 케이스에 대한 $Q$ 의 합은 $2\,000$ 이하이다.
3	27	모든 테스트 케이스에 대한 $Q$ 의 합은 $200\,000$ 이하이다.
4	46	추가적인 제약이 없다.

Input

Output

1 2 -3 4 5
-4 1 2 3

첫 번째 테스트 케이스에서 첫 쿼리 후 수열은 $[1,-4,-3,-2,5]$ 가 된다. 두 번째 쿼리 후에는 다시 $[1,2,3,4,5]$ 가 되고, 마지막 쿼리 후에는 $[1,2,-3,4,5]$ 가 된다.