ABC106D - AtCoder Express 2

atcoder.jp

問題概要

駅(N<=500)間を結ぶ特急列車がM台（<=200000)あります。 　
２つの駅間で完結する列車の数を求めるキュー（M<=100000)に答えます。

検討

昨晩のバチャで初挑戦した問題ですが，どう解いていいのかわかりませんでした。 　

多数のキューがある問題なので愚直にやるとTLEしそうです。 　
累積和などの前処理を考えるのだろうとまでは考えましたがそれ以上は考えつきませんでした。
　
解説ACです。 　

始発駅と終着駅を二次元の座標にとって，二次元累積和をとればよい，というのはなるほどです。 　
おいしいたこ焼きの焼き方（ D - おいしいたこ焼きの焼き方 ）とこの問題が同じテクニックで同じように解けるのが面白いです。
　
これ，３次元以上の場合も直方体の体積を求めるみたいな感じで解けそうですね。 　

運行期間の時間軸を入れた更に難しい問題などもできそうです。とても複雑そうですが。 　

解き方がわかればシンプルな問題で５分ほどで書けました。

ACしたコード

#include <bits/stdc++.h> 
using namespace std; 
int E[510][510]={}; 
int dp[510][510]={}; 
int main(){ int N,M,Q,ans; 
cin>>N>>M>>Q; 

//入力
  int l,r; for(int i=1;i<=M;i++){ cin>>l>>r; E[l][r]++; } 

//累積和計算 
 for(int i=1;i<=N;i++){ 
  for(int j=1;j<=N;j++){ 
   dp[i][j]=dp[i-1][j]+dp[i][j-1]+E[i][j]-dp[i-1][j-1]; 
  } 
 } 

//キュー処理 
 int p,q; for(int i=0;i<Q;i++){ 
 cin>>p>>q; 
 ans=dp[q][q]-dp[p-1][q]-dp[q][p-1]+dp[p-1][p-1]; 
 cout<<ans<<endl;
} 

return 0; 
}