Educational Codeforces Round 10 C. Foe Pairs

http://codeforces.com/contest/652/problem/C

問題概要

順列 p と相性の悪い数のペア (a_i, b_i) が与えられる。相性の悪いペアを含まないような連続する部分列はいくつあるだろうか。

解法

左端を i に固定し、p[i,j] が相性の悪いペアを含むような最小の j を求める。

こうすると左端が i であるような相性の悪いペアを含まない部分列の個数は j-i 個になる。

j は i に対して単調増加なので尺取法が可能。

Educational Codeforces Round 10 C. Foe Pairs

妙に考えこんでしまった。