Mysterious Sequence(CC:MYSAR)
\(N\) 要素からなる、数列 \(A\) があります。
あなたは、この数列に以下のクエリを尋ねることができます。
Q l1 r1 l2 r2
- \( \max(A_{l1},A_{l1+1},...,A_{r1}) - \min(A_{l2},A_{l2+1},...,A_{r2})\) の値を求める。
\( A_1 , A_N \) の値のみ、初めに与えられます。
このクエリを \(2 \times N\) 回まで使って、数列 \(A\) を特定してください。
- \(2 \le N \le 10^5\)
- \( N \) は偶数
- \(1 \le A_i \le 10^9 \)
とりあえず、クエリの使い方として、パッと思いつくのは Q 1 2 1 2 のような用法でしょうか。これで \( |A_1 - A_2| \) は分かります。しかし、大小関係がうまく分からなさそうなので、この方針ではうまく行きません。
ここで、「 \(N\) は偶数」という制約に着目します。この制約がないと嬉しくない…ということは、もしかすると、例えば「 \(A_i\) と \(A_{i+2}\) の間」のような飛び飛びの情報が嬉しくて、両端からうまいこと交互に特定できる、という可能性があります。こうなると、隣接3項間の関係に着目したくなります。
あと、ざっくりとした感覚として、より広い範囲を取ると情報量が減ってしまうという直感が働きます。
ここまでを踏まえ、隣接3項間に Q i i+1 i+1 i+2 , Q i+1 i+2 i i+1 を聞いてみたいと思います。
簡単のため、3つの値の大小関係を {大,中,小} とでもして試しましょう。
Q i i+1 i+1 i+2を1クエリ目、Q i+1 i+2 i i+1を2クエリ目とします。値の大小関係 / 1クエリ目 / 2クエリ目 と、全パターン並べてみると、
大中小 / 大 - 小 / 中 - 中
大小中 / 大 - 小 / 中 - 小
中大小 / 大 - 小 / 大 - 中
中小大 / 中 - 小 / 大 - 小
小大中 / 大 - 中 / 大 - 小
小中大 / 中 - 中 / 大 - 小
中中小 / 中 - 小 / 中 - 中
中小中 / 中 - 小 / 中 - 小
小中中 / 中 - 中 / 中 - 小
中小小 / 中 - 小 / 小 - 小
小中小 / 中 - 小 / 中 - 小
小小中 / 小 - 小 / 中 - 小
小小小 / 小 - 小 / 小 - 小
赤は値が大きい方、緑は実は0である値を示します。
この表をよく睨むと、
- (クエリ1) > (クエリ2) ⇔ 値が \(A_i > A_{i+2}\)
- (クエリ1) = (クエリ2) ⇔ 値が \(A_i = A_{i+2}\)
- (クエリ1) < (クエリ2) ⇔ 値が \(A_i < A_{i+2}\)
- さらに、その差の絶対値 = | (クエリ1の値) - (クエリ2の値) | が成立する。
やはり、飛び飛びの関係が得られました。これを実装すると、ACできます。
https://www.codechef.com/viewsolution/40632088
