Codeforces Round #630 (Div. 2) G. No Monotone Triples

お題箱より。けっこう難しかった…

問題概要

数列 $a_{1}, ..., a_{n}$ が与えられる。この数列の長さ $3$ 以上の部分列が「free from monotone triples」であるということを、「その部分列からさらに長さ $3$ の部分列をどのように取っても、広義単調増加にも広義単調減少にもならない」ことと定義する。

以下の $q$ 個のクエリに答えよ。

整数 $L, R$ が与えられる。 $a_{L}, ..., a_{R}$ の部分列であって「free from monotone triples」であるものが存在すれば、その中で最長のものを1つ求めよ。存在しない場合は $0$ を出力せよ。

手やプログラムで実験してみると、長さ $5$ 以上の数列は必ず単調な長さ $3$ の部分列を含むことが分かります。よって、条件を満たす長さ $3$ の部分列を探すこと、長さ $4$ の部分列を探すことをそれぞれ行えば良いです。

※長さ $3$ について解くだけならもう少し楽な方法があるのですが、後の長さ $4$ の解法に繋がるような方法で書きます。

作りたい $3$ つ組を $(b_{1}, b_{2}, b_{3})$ と表記します。長さ $3$ で条件を満たす部分列は、

のいずれかを満たすものです。前者を例に解説します。

目標は各要素 $a_{1}, ..., a_{n}$ について、その要素を $b_{3}$ としたときに $b_{1}$ が最も近くにある $3$ つ組を（もし存在すれば）求めることです。クエリで指定された区間になるべく含まれて欲しいので、これらだけを考えれば十分です。

$a_{i}$ を左から順番に見ていきながら、スタックで以下のような列を管理します。（実際にはランダムアクセスしたいので vector 等でやるのが良いです）

f:id:betrue12:20200419142922p:plain

つまり $a_{i}$ を起点として「自分より左側にあって、値が自分以上である一番近い要素」を連鎖的に取っていき、そのインデックスを管理したものです。

$a_{i}$ を右端 $b_{3}$ とした $3$ つ組を見つける時には、以下の手順を踏みます。

f:id:betrue12:20200419142934p:plain

1と3の手順はスタックに対して二分探索すれば良いです。2の手順では、1度スタックに入って追い出された要素のインデックスをBITなどで管理すれば二分探索で求めることができます。

これが最適であることは、

という2点を確認することで示せます。

これで考えるべき $3$ つ組を抽出できました。各クエリについての判定は、 $3$ つ組とクエリの区間をともに右端ごとに分類し、 $a_{i}$ を左から順番に見ていきながら

とすれば良いです。

作りたい $4$ つ組を $(b_{1}, b_{2}, b_{3}, b_{4})$ と表記します。実験をすると、 $4$ つ組が条件を満たすためには

が必要十分であると分かります。

先ほどと同様に、各要素 $a_{1}, ..., a_{n}$ について、その要素を $b_{4}$ としたときに $b_{1}$ が最も近くにある $4$ つ組を（もし存在すれば）求めることを目指します。先ほどは左上に伸びるスタックを管理しましたが、今後は左下に伸びるスタックも同様に管理します。

f:id:betrue12:20200419143435p:plain

手順も先ほどとほぼ同様です。

まずつのスタックの中に対して以下の値をそれぞれ求め、より左側にあるほうをとする。
- 左上に伸びるスタックの中で、 $a_{i}$ より大きい一番右側の要素。
- 左下に伸びるスタックの中で、 $a_{i}$ より小さい一番右側の要素。
$x$ より左側にあって最も近い「どちらのスタックにも含まれていない要素」を探し、その要素を $b_{1}$ とする。
それぞれのスタックにおいて、 $b_{1}$ より右側にあって最も近い「スタックに含まれている要素」を、並び順に $b_{2}, b_{3}$ とする。