Codeforces Round #506 (Div. 3)C. Maximal Intersection

$n$ 個の区間 $[l_i ; r_i]$ が与えられる. この中から一つの区間を取り除くことができるとき, 残された区間の共通部分の長さの最大値はいくらか.

$n$ 個から一個除いた時の解は？という問題で, もし累積的に計算可能な構造をしている場合, 左右両方からの累積和による計算を疑うべきです. この問題もそのように求めることができます.

$left_i :=$ (左から $i$ 個の区間の共通区間), $right_i :=$ (右から $i$ 個の区間の共通区間)みたいに定義すれば, 一つ除いた時の共通区間は簡単に計算できます.