CodeForces - 1000C Covered Points Count 思维

CodeForces - 1000C Covered Points Count

题意：

给你 n 段区间，分别输出输出被覆盖 1~n 次点的个数

思路：

把每段区间存起来，起点标记为 1 ，终点标记为 -1，按照点的顺序排序。存储时为了防止终点对起点的影响，需要将终点的位置加 1 。

比如 
3 
0 3 
1 3 
3 8 
这组样例，排完序之后的顺序就是图中绿色的编号。 

我们发现，1点的标记是1，二点的标记也是1，证明他们都是起点，一开始我们设一个计数变量，我们发现点被覆盖的次数就是计数变量原来的值加上当前点的标记，这就是为什么要给起点终点标记为1，-1了。然后到达一个起点或终点的时候，只需要后边的点的编号减去前边的点编号就是我们要的被覆盖的点的个数了。 
但是有个地方就变得很难处理了，我们发现345这三个点重合了，按照原来的方式求的就不对了。怎么办呢。 
只要把终点往后移一个就ok了。 
 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
map<ll,ll> ans;
ll s[maxn]={0};
int main()
{
    int n;
    ll x,y;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        y++;
        ans[x]++,ans[y]--;
    }
    ll l=0,cnt=0;
    for(map<ll,ll>::iterator i=ans.begin();i!=ans.end();i++)
    {
        s[cnt] += (i->first-l);
        l = i->first;
        cnt += i->second;
    }
    for(int i=1;i<n;i++)
        printf("%lld ",s[i]);
    printf("%lld\n",s[n]);
    return 0;
}