ABC 247 E — Max Min

考察

最大値が X、最小値が Y なら、区間内の全要素は Y≤A_i≤X であり、さらに X と Y を少なくとも 1 回ずつ含む必要がある。

Y 未満または X 超の要素はどの有効区間にも含められず、列を独立な区間へ分断する境界になる。

採用する候補: 右端 R を左から動かし、直近の X、直近の Y、直近の範囲外要素の位置を持って、有効な左端数を加算する。

棄却する候補: 全 L,R を列挙し、各区間の最大値・最小値を更新または query して条件を判定する。

区間が二次個あり、N≤2×10^5 では最大最小を高速化しても列挙自体が間に合わない。

lastX,lastY,lastBad を未出現値で初期化する。A_R が X,Y なら対応位置を R に更新し、範囲外なら lastBad=R とする。その後 max(0,min(lastX,lastY)-lastBad) を 64 bit の答えへ加える。

典型の発動条件

右端固定の区間数え上げ

発動条件: 区間条件を満たす左端が、右端ごとに連続した index 範囲になるとき。

必要値の直近出現位置と禁止境界から、有効な L の個数を差で求める。

直近位置の tracking

発動条件: 区間が特定要素を含む条件と、含んではならない要素の境界を同時に管理したいとき。

lastX,lastY で包含条件、lastBad で全要素が [Y,X] 内という条件を表す。

問題固有の要素

最大・最小の等号条件は、範囲外要素を境界として除いた後なら『X と Y を含む』だけになる。

別の問題へ持ち帰る視点: 区間の extremum 条件では、許容範囲外を separator にしてから境界値の出現条件へ変換する。

正当性

固定した R で L>lastBad なら全要素は範囲内であり、X と Y の両方を含む条件は L≤min(lastX,lastY) になる。 したがって右端 R の寄与は max(0,min(lastX,lastY)-lastBad) で、全 R の寄与を足せば各区間をちょうど一度数える。 各右端に対する全条件を 3 個の index で表せ、X=Y も同じ式で線形に数えられる。

実装上の注意

  • X=Y のときは同じ A_R で lastX と lastY の両方を更新すれば式を変えずに使える。
  • 区間数は N(N+1)/2 まで達するため、答えは 64 bit 整数で保持する。

復習の核

  • X=Y の全要素一致例と、範囲外要素をまたげない例について、ある R の有効な L の範囲を実際に書かせる。

計算量と制約

時間

O(N)、三last位置。

空間

O(1)補助、入力保存時O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 1 \leq A_i \leq 2 \times 10^5; 1 \leq Y \leq X \leq 2 \times 10^5; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Max Min の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 局所寄与へ分解して集計順を交換する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 寄与の数え上げと順序交換

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: 局所寄与へ分解して集計順を交換する

      • 数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。

      この解説で扱わないこと:

      • active集合を時刻・座標順に更新するevent sweep、更新列を逆から読むだけの処理、および成分ごとの解を単に掛け合わせる構造判定。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題