ABC476 E - Min-Max Swap

考え方

区間内の最大値と最小値を高速に取得する方法さえ知っていれば、それ以外はC問題レベル。
逆写像を作っておくことで、最大値と最小値の位置を高速に調べる。
そして、それら $2$ つの位置の情報を入れ替える。

さて、区間内の最大値と最小値を高速に取得する方法だが、これはsegment木でよい。
同じsegment木で最大も最小も求められるようにしてもよいし、segment木を $2$ つ作ってもよい。
$2$ つの位置の情報を入れ替えるときに、segment木上の情報も入れ替える。
ただ、これだけである。

計算量は $O((N+M)\log N)$ である。

入力例1での動作

入力を受け取る。

n: 5
m: 3
p: {3, 1, 4, 2, 5}
query:
  {1, 3}
  {1, 5}
  {1, 4}

最初に、値から現在位置を引けるように逆写像 pos を作っておく。
pos[x] は、値 $x$ が p の何番目にあるかを 0-indexed で表すものとする。
pos[0] はダミーとして、初期状態は次のようになる。

p:   {3, 1, 4, 2, 5}
pos: {-, 1, 3, 0, 2, 4}

また、区間最大値と区間最小値を取得できる segment 木を用意する。

最初のクエリは区間 $[1,3]$ である。
この区間の最小値は $1$、最大値は $4$ で、pos[1]=1、pos[4]=2 からそれぞれ p の $1$ 番目、$2$ 番目にある。
この $2$ つの位置を入れ替え、逆写像も更新すると、次のようになる。

p:   {3, 4, 1, 2, 5}
pos: {-, 2, 3, 0, 1, 4}

segment 木の情報も、この入れ替えを反映して更新する。

次のクエリは区間 $[1,5]$ である。
この区間の最小値は $1$、最大値は $5$ で、pos[1]=2、pos[5]=4 からそれぞれ p の $2$ 番目、$4$ 番目にある。
この $2$ つの位置を入れ替え、逆写像も更新すると、次のようになる。

p:   {3, 4, 5, 2, 1}
pos: {-, 4, 3, 0, 1, 2}

segment 木も同様に更新する。

最後のクエリは区間 $[1,4]$ である。
この区間の最小値は $2$、最大値は $5$ で、pos[2]=3、pos[5]=2 からそれぞれ p の $3$ 番目、$2$ 番目にある。
この $2$ つの位置を入れ替え、逆写像も更新すると、次のようになる。

p:   {3, 4, 2, 5, 1}
pos: {-, 4, 2, 0, 1, 3}

したがって、答えは

3 4 2 5 1

である。

注意点

特になし。

別解

特になし。