前缀和

Karen and Coffee 前缀和区间计数

题源 codeforces Round 816 B

题意
简单说就是给你一个大区间,每次给你一条线段,给出后线段上所有数计数 +1
询问若干个区间,问区间内大于等于给定常数k的个数有多少?

思路
扫描线可写,但是无论是数状数组和线段树写起来都非常麻烦……
最简单的正解就是很久很久没用的前缀和累加计数

前缀和累加计数
每次给定一个区间[l,r],则ary[l]++,ary[r+1]--
最后扫一边,累加ary[i] 即得当前下标 i 的数值。
很好理解我就不解释了

ACcode

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

const int maxn = 2e5 + 5;

int n, k, q, l, r, tmp;
int ary[maxn];
int sum[maxn];

int main()
{
    scanf("%d %d %d", &n, &k, &q);
    while (n--) {
        scanf("%d %d", &l, &r);
        ary[l]++;
        ary[r + 1]--;
    }
    for (int i = 1; i < maxn; i++) {
        tmp += ary[i];
        sum[i] = tmp >= k ? sum[i - 1] + 1 : sum[i - 1];
    }
    while (q--) {
        scanf("%d %d", &l, &r);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注