ABC106 D - AtCoder Express 2

問題

n個の都市とm本の列車があり、i本目の電車は区間[li, ri]を走っている
各クエリで[l,r]に「走る区間が完全に含まれる」ような列車の本数を出力する

n<=500, m<=2*10^5, q<=10^5

解法

区間[l,r]を走る列車について考える
これを二次元平面上の (y座標,x座標) = (l,r) の点とみなすと、この列車を完全に含むような区間は、y<=l(∴ 区間の左端がl以下)かつr<=x(∴ 区間の右端がr以上)の範囲全てになる
だからまずは各列車を点とみなしたときの座標に+1しといて、それらを右と上に伸ばしておけば(O(N^2)の二次元累積和)、各クエリにO(1)で答えられるようになる

制約からO(QN)が間に合うから各行[列]で一次元累積和してクエリごとにO(N)が基本的な想定解だったらしい
そこまで辿り着けたなら二次元累積和した方が早くね？

実装

dpではない

int n, m, q, l, r, dp[505][505];

signed main() {
	cin >> n >> m >> q;
	rep(i,m) {
		cin >> l >> r;
		dp[l][r]++;
	}
	rep(i,501) rep(j,501) dp[i][j+1] += dp[i][j];
	rep(j,501) for(int i=500; i>0; --i) dp[i-1][j] += dp[i][j];
	while (q--) {
		cin >> l >> r;
		cout << dp[l][r] << endl;
	}
}