#419 Div2 Problem B Karen and Coffee (统计区间重叠部分 && 前缀和)

题目链接：http://codeforces.com/contest/816/problem/B

题意：给出 n 表示区间个数，限定值 k 以及问询次数 q，当一个数被大于或等于 k 个区间重复覆盖时才算有效数，每一次问询都是以区间方式给出，例如(L， R)问你在这个L~R的范围内有多少个数是有效数(即包含这些数的区间个数>=k)。

分析： 这题可以预先统计哪些数被大于或者等于 k 个原始区间重复覆盖，只要提前将这些满足条件的数递增地编上权值构成前缀和序列，然后对于每段问询只要将前缀和序列做个减法即可，例如找到了 a1 a2 a3这三个数构是满足条件的，令sum[a1]=1，sum[a2]=2，sum[a3]=3，如果问询(a2，a3)这个区间满足条件的数，则只要将对应的权值做个减法即可，即sum[a3] - sum[a2-1]。关于如何统计有效的数，可以这样做，令arr数组存储的是区间信息，对于给出的 n 个区间 (L，R)，只要将arr[L]++，arr[R+1]--（R+1相当于区间结束标识，这种技巧在POJ Matrix这题便有涉及），然后采用动态规划从前往后扫一遍和，当和>=k的时候那此时这个点便是满足条件的，给其加上权值构建前缀和序列。可能说的有点乱，看代码即知。

#include<bits/stdc++.h>
using namespace std;
;
int arr[maxn], sum[maxn], cnt[maxn];
int main(void)
{
    int n, k, q;
    scanf("%d %d %d", &n, &k, &q);
    ; i<n; i++){
        int L, R;
        scanf("%d %d", &L, &R);
        arr[L]++, arr[R+]--;
    }
    sum[] = arr[];
    ; i<maxn; i++){
        sum[i] = sum[i-] + arr[i];//记录从左到右扫出来的和，其实这个和就代表了区间的个数，由每个区间的左端点贡献
        cnt[i] = cnt[i-] + (sum[i]>=k);//cnt为前缀和序列，如果当前的和>=k则对这个点在前缀和序列+1
    }
    while(q--){
        int L, R;
        scanf("%d %d", &L, &R);
         printf(]);
    }
    ;
}

巴特西

#419 Div2 Problem B Karen and Coffee (统计区间重叠部分 && 前缀和)

最新文章

热门文章