AtCoder Regular Contest #014, D : grepマスター

問題文

http://arc014.contest.atcoder.jp/tasks/arc014_4

解法

クエリを処理するとき、ヒットした行自体は必ず含まれるので N 行は確定します。
また、端の部分は上端が で、下端は です。

次に、ヒットした行の間の部分について考えます。
間が x + y 以上空いていれば、その部分は x + y 行出力されます。
そうでない場合、その間の行数分だけ出力されます。
各クエリ毎に、x + y 以上空いている部分の数と、それ以外の部分の総和を高速に求められればよい、ということになります。

ある値以上空いている区間の数は、予め という列を作ってソートしておくと、二分探索により で求められます。
また、列はソート済みなので、x + y に満たない区間は列の中で連続しています。
従って、予め累積和を計算しておくことで、x + y に満たない値の総和を で求められます。（境界となるインデックスは先程の二分探索で求まっている）
各クエリを で処理できるので、全体では で答えを出すことができます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int all, n, m;
	cin >> all >> n >> m;

	VI ls( n );
	FOR( l, ls )
	{
		cin >> l;
	}

	VI spaces;
	REP( i, 0, n - 1 )
	{
		spaces.PB( ls[ i + 1 ] - ls[i] - 1 );
	}

	sort( ALL( spaces ) );
	VI csum( 1, 0 );
	partial_sum( ALL( spaces ), back_inserter( csum ) );

	REP( i, 0, m )
	{
		int x, y;
		cin >> x >> y;

		int res = n;
		int pos = lower_bound( ALL( spaces ), x + y ) - spaces.begin();
		res += ( n - 1 - pos ) * ( x + y );
		res += csum[ pos ];
		res += min( ls[0] - 1, x );
		res += min( all - ls.back(), y );

		cout << res << endl;
	}

	return 0;
}