解题思路
区间 \(dp\)。
划分阶段：以左右城市之间的列车数量为阶段。
状态表达：设 \(f_{i,j}\) 为城市 \(i\) 与城市 \(j\) 之间的列车数量。
状态转移：
由图可知，城市 \(l\) 与城市 \(r\) 之间的列车数量，就是城市 \(l\) 与城市 \(r-1\) 之间的列车数量与城市 \(l+1\) 与城市 \(r\) 之间的列车数量（蓝色括号）加上刚好从城市 \(l\) 到城市 \(r\) 的列车数量，但是还有一个重合部分，也就是城市 \(l+1\) 与城市 \(r-1\) 之间的列车数量（橙色方框）。
所以，城市 \(l\) 与城市 \(r\) 之间的列车数量就等于城市 \(l\) 与城市 \(r-1\) 之间的列车数量与城市 \(l+1\) 与城市 \(r\) 之间的列车数量减去城市 \(l+1\) 与城市 \(r-1\) 之间的列车数量加上刚好从城市 \(l\) 到城市 \(r\) 的列车数量。
即：
\[f_{i,j}=f_{i,j}+f_{i,j-1}+f_{i+1,j}-f_{i+1,j-1} \]初始状态：求出刚好从城市 \(i\) 到城市 \(j\) 的列车数量；即：f[l[i]][r[i]]++;。
求解目标：\(f_{p,q}\)；
代码
#include<bits/stdc++.h>
#define ri register int
using namespace std;
int n,m,q;
int l[200005],r[200005],f[505][505];
int main(){
cin>>n>>m>>q;
for(ri i=1;i<=m;i++){
cin>>l[i]>>r[i];
f[l[i]][r[i]]++;
}
for(ri i=1;i<=n;i++)
for(ri j=1;j<=n;j++)
f[i][j]+=f[i+1][j]+f[i][j-1]-f[i+1][j-1];
while(q--){
int u,v;
cin>>u>>v;
cout<<f[u][v]<<'\n';
}
return 0;
}