問題概要
$\mathbb Z$ 上の閉区間の集合 $\mathcal I$ ($| \mathcal I | = n$) が与えられる．$\mathcal I_i = [ L_i, R_i ]$ である．また，整数 $m $ が与えられる．
以下の条件を満たす整数の順序対 $( l, r )$ の個数を求めよ：
- $1 \leq l \leq r \leq m $
- $\forall i \in \{ 1, 2, \dots, n \}, \mathcal I_i \not \subseteq [ l, r ]$
制約
- $1 \leq n, m \leq 2 \times 10^5$
- $1 \leq L_i \leq R_i \leq m $
解法
もし可能であればやりたいことは順序対 $( l, r )$ を全探索することですが，素朴にやると $\Theta( m^2 )$ 個あって TLE するのでそれはできません．なので，より弱い要請として片方だけを固定するとうれしいことがあるかを考えます．
$( l, r )$ の内 $l$ を固定したとき，$r$ について何が言えるかを考えていきます．固定した $l$ に対して条件を満たす $r$ があったとします．このとき，$r' \leq r$ であるような $r'$ についても，区間 $[ l, r ]$ に包含されず，より狭い区間 $[ l, r' ]$ に包含される区間 $\mathcal I_i$ は存在しない*1ので条件を満たします．逆に，条件を満たさない $r$ があったとすれば，$r' \geq r$ であるような $r'$ についても，区間 $[ l, r ]$ に包含されていた区間は区間 $[ l, r' ]$ にも包含されることから，条件を満たしません．ある $r$ が条件を満たすか否かは（計算方法はともかく）一意的に定まるはずなので，整数 $\mathit{ opt }( l )$ であって，$l \leq r \leq \mathit{ opt }( l )$ であるような $r$ は条件を満たし，$\mathit{ opt }( l ) < r \leq m $ であるような $r$ は条件を満たさない $\mathit{ opt }( l )$ があることになります．更に，$l' > l$ なる $l'$ について考えると，ある $r$ があって $[ l, r ]$ に包含されず $[ l', r ]$ には包含されるような区間 $\mathcal I_i$ は存在しない*2ので，そういうものに対処するために $r$ を左に動かす必要はありません．よって，$\mathit{ opt }( l ) \leq \mathit{ opt }( l' )$ であると言えます．$l$ を右に動かすにつれて $r$ も右方向にしか動かないため，「しゃくとり法」と呼ばれるテクニック (see [1]) を使うことで，$l, r$ を動かす回数を $\Theta( m )$ に抑えられます．
具体的な実装を考えるために，条件について扱いやすい言い換えが無いか考えてみます．ある $l, r$ に対し，区間 $\mathcal I_i$ が区間 $[ l, r ]$ に包含されることは，$[ l, r ]$ 内にある $\mathcal I_i$ の端点がちょうど $2$ 個であることと言えます．よって，各 $i$ について $[ l, r ]$ 内にある $\mathcal I_i$ の端点の個数を管理し，更に個数が $2$ であるような $i$ の個数を別途管理することで実装できます．具体的には，$r$ を右に動かすときに新たに $[ l, r ]$ に含まれる端点についてその区間の番号に紐づけた値をインクリメントし，$l$ を右に動かすときに区間から外れる端点についてその区間の番号に紐づけた値をデクリメントするようにすればよいです．これを配列（なり std::vector なり）で実装すれば，各端点はちょうど $2$ 回処理されることから，$l, r$ の移動と合わせて $\Theta( n + m )$ 時間のアルゴリズムが得られます．
コード
int main() { IN( int, N, M ); VI L( N ), R( N ); REP( i, N ) { cin >> L[i] >> R[i]; --L[i], --R[i]; } VVI endpoints( M + 1 ); REP( i, N ) { endpoints[ L[i] ].PB( i ); endpoints[ R[i] ].PB( i ); } LL res = 0; VI included( N ); int tows = 0; for ( int l = 0, r = 0; l < M; ++l ) { for ( ; tows == 0 && r <= M; ++r ) { FOR( p, endpoints[r] ) { tows += ++included[p] == 2; } } res += ( r - 1 ) - l; FOR( p, endpoints[l] ) { tows -= included[p]-- == 2; } } cout << res << endl; return 0; }
参考文献
[1] 秋葉拓哉; 岩田陽一; 北川宜稔. プログラミングコンテストチャレンジブック ~ 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~. マイナビ出版, 2012.
