Part I Preface
Part II Sketch
- 给定正整数 \(n, m, q\)。
- 接下来给定 \(m\) 组 \(x_i, y_i\)，表示一列列车的起始站和终点站。
- 在接下来给定 \(q\) 组 \(l_i, r_i\)。
- 对于每组询问，回答有多少 \(x_i \geq l_i \operatorname{and} y_i \leq r_i\)，即有多少列列车的全程都包含在 \(l_i, r_i\) 间。
- \(1 \leq n \leq 500\)。
- \(1 \leq m \leq 200000\)。
- \(1 \leq q \leq 100000\)。
- \(1 \leq x_i \leq y_i \leq n\)。
- \(1 \leq l_i \leq r_i \leq n\)。
Part III Analysis
简单思考不难发现， \(l_i\sim r_i\) 中的列车数量即为 \(l_i\sim r_i - 1\) 中的列车数量加上 \(l_i + 1\sim r_i\) 中的列车数量。但是 \(l_i + 1\sim r_i - 1\) 中的列车被算了两次，重复了，我们要去掉一个。
所以 \(l_i\sim r_i\) 中列车的数量就等于 \(l_i\sim r_i - 1\) 中的列车数量加上 \(l_i + 1\sim r_i\) 中列车的数量减去 \(l_i + 1\sim r_i - 1\) 中列车的数量。若用 \(dp(i, j)\) 表示 \(i\sim j\) 中列车的数量，状态转移方程即为：
\[dp(i, j) = dp(i, j - 1) + dp(i + 1, j) - dp(i + 1, j - 1)
\]
输入时，每次输入一列列车的起始站和终点站 \(x_i, y_i\) 时，我们直接给 \(dp(x_i, y_i)\) 自增即可，这就是初始状态。最终输出每个 \(dp(l_i, r_i)\) 即可。
注意因为我们每次计算时都用到了 \(i + 1\) 这一层的信息，所以我们枚举 \(i\) 时需要从 \(n\sim 1\) 进行遍历。
Part IV Code
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') w = -1;
ch = getchar();
}
while(isdigit(ch)){
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
inline void write(int x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, q;
int dp[N][N];
int main(){
n = read(), m = read(), q = read();
while(m--) dp[read()][read()]++;
for(int i = n; i >= 1; i--)
for(int j = i; j <= n; j++)
dp[i][j] += dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
while(q--) write(dp[read()][read()]), putchar('\n');
return 0;
}