ABC106 D AtCoder Express 2
https://beta.atcoder.jp/contests/abc106/submissions/3067332
問題概要
列車が走っている区間l,rがN個与えられる。クエリp,qがQ個与えられる時、各クエリにおいて[p,q]に完全に含まれる列車の数を求めよ。N<=500、Q<=100000である。
取った方針
dp[l][r]に[l,r]に完全に含まれる列車の本数の和を記録することとする。
すると、dp[l][r] = dp[l-1][r]+[l][r-1]+dp[l][r] で表せる気がする。
この時、dp[l][r]は区間[l,r]を走る列車の本数で初期化されているものとする。
[r,r]は[r-1,r]に含まれ、[r-1,r]は[r-2,r]に含まれるので、[l+1,r]に含まれる電車の本数は[l+1,r]を走る電車の本数 + [l+2,r]を走る電車の本数 ... [r,r]を走る電車の本数で表すことができる。
右端についても同様のことができるので、lが大きい順、rが小さい順に値が確定するように表を更新していけばよい。(dpではない気がしてきた)
正しい方針(解説の方針)
列車の走る区間、クエリともに区間の左端/右端しかないので、二次元配列で考える。(賢すぎワロタ)
二次元配列で考え、x[p][q]を[p,q]を走る電車の本数とすると、クエリ(p,q)の答えは、x[p][p]+x[p][p+1]+...+x[p][q]+...x[q][q]となる。
これは累積和を使うと高速に求められ、制約的に1次元累積和を行ってクエリ1つにNかけても十分間に合う。
とか言いつつここまで考えられたら先に二次元累積和が見えると思うんですけど!
得られた知見
・出てくる制約が一つだけ弱い->そこに注目
・考える要素が2つしかない(ex:区間)->二次元座標で考えてみる
解くのに必要な要素
・区間[l,r]が出てきたらその解を表x[l][r]に入れてみようと思う心
・累積和
周辺調査によって得られた知見
なし