Codeforces 1000C Covered Points Count 【前缀和优化】-白红宇

Codeforces 1000C Covered Points Count 【前缀和优化】

阅读量：4551 次

发布时间：2019-06-08

本文共 1047 字，大约阅读时间需要 3 分钟。

想到这道题的解法是建个数组，每读入一条线段进来，就把这线段上的每个点+1，最后扫一遍数组算出count数组，这么做的复杂度是n*max(a[i])；简单用前缀和优化，复杂度变为n+max(a[i])还是过不了。我们想到a[i]是10^18级别的，而n最大200000，所以可以想象出这个前缀和数组里面大多数都是0（有很多是零的连续区间），然后每个0的连续区间维护出来的前缀和都是一样的【很多的计算力耗费在这个上面了】，所以我们想到只考虑不是0的地方，然后新的不是0的地方和上一个不是0的地方之间的点被线段覆盖次数是一样的。不是0的地方有n级别个，由于我们用map维护（要把所有端点从左到右排序），所以O（nlogn）复杂度。

map的遍历看代码

#include
     
      #include
      using namespace std;map
       
         m;long long count[200005];int main(){    int n; cin>>n;    for(int i=1;i<=n;i++){        long long start,end; scanf("%lld%lld",&start,&end);        m[start]++; m[end+1]--;    }            long long last=0;    int cnt=0;        //考虑每个区间     for( map
        
         ::iterator it = m.begin(); it!=m.end(); it++){
            if( it==m.begin() ) { last=it->first; cnt+=it->second;  continue; }        count[ cnt ] += it->first - last;        last=it->first;         cnt+=it->second;    }        for(int i=1;i<=n;i++) cout<
         
          <<" ";        return 0;}

转载于:https://www.cnblogs.com/ZhenghangHu/p/9239757.html

你可能感兴趣的文章