文章

85

粉丝

0

获赞

315

访问

6.1k

头像
刷出一道墙 题解:差分数组
P1209
发布于2026年3月6日 18:37
阅读数 65

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005; // 根据题目范围调整,如果坐标范围不大可以用这个

int diff[MAXN];

int main() {
    int start, end;
    int maxR = 0;

    // 读墙区间,构建差分数组
    while (scanf("%d %d", &start, &end) != EOF) {
        if (start == 0 && end == 0) break;
        diff[start]++;
        diff[end + 1]--;
        if (end > maxR) maxR = end;
    }

    // 前缀和,得到每个点的覆盖次数
    vector<int> cover(maxR + 2, 0);
    int sum = 0;
    for (int i = 0; i <= maxR + 1; i++) {
        sum += diff[i];
        cover[i] = sum;
    }

    // 读查询
    int q1, q2;
    while (scanf("%d %d", &q1, &q2) != EOF) {
        if (q1 == 0 && q2 == 0) break;
        for (int i = q1; i <= q2; i++) {
            printf("%d\n", cover[i]);
        }
    }

    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发