JOISC2015 - 防壁
解法
区間を二次元平面上の点とみなす（典型）
操作は次のように言い換えられる
$ x \lt kである点を$ (k, y + k - x)に動かす。
$ y \gt kである点を$ (x + k - y, k)に動かす。
図を書いて実験してみるとわかりやすいが、何回か操作を行った後の点の分布は、
平面上の左上部分の長方形領域に属する点
長方形の境界を除く内部の点は一度も動かされていない
長方形の下および右の辺上の点は、それまでの操作で右上のみに動かされたか、左下のみに動かされた
上記の長方形の右下の頂点からつながっている折れ線上にある点
の二通りに分けられる。
区間の長さ、すなわち$ y - xの昇順にソートしておくと、折れ線上にある・ないが単調になって扱いやすい。
折れ線上の点を線分ごとにまとめて管理する。操作によって$ n個の線分が動かされる場合、$ n - 1個以上の線分が消えてまとめられるので、愚直に処理してよい。BIT などを使うと動いた距離が計算できる。
それ以外の点は、初めて折れ線に含まれるタイミングにおいて、一方向にしか動かされていないので、その時点での座標ともとの座標からそれまでに動いた距離が簡単に計算できる。
うまく実装すると通る