[AT_ABC106_D]题解(C++)

Part I Preface

• 原题目\(\text{(Luogu)}\)
• 原题目\(\text{(AtCoder)}\)

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\) 中列车的数量，状态转移方程即为：

输入时，每次输入一列列车的起始站和终点站 \(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;
}