题目网址点击打开链接
思路:把每个线段的起点终点都放进vector容器，起点标记为1，终点标记为0，然后排序，按坐标从小到大排序，若坐标大小相等，则按标记从大到小排序，即起点排在终点的前面（看别人的博客说这个操作是叫离散化）。排完序之后从头到尾扫一遍即可,我定义了一个cnt是计数器，用来记线段的数量，每到一个起点，cnt++表示该起点到后面一个点的这部分区间里的所有点被cnt个区间覆盖，到终点cnt--表示该点到下一个点的这部分区间的所有点被cnt个线段覆盖，每扫到一个点有8种情况（2*2*2）要分类讨论，（1.是否是起点 2.前面遍历的一个点是否是起点 3.目前遍历到的点和前面的那个点的坐标是否相同）.还有要注意坐标是long long
#include<bits/stdc++.h>
using namespace std;
int maxn=2*100000+5;
long long ans[2*100000+5];
struct node
{
long long x;
int y;//x表示坐标,y是标记,起点标记1,终点标记0
node(long long xx,int yy){x=xx;y=yy;}
};
vector<struct node>v;
bool cmp(const node&a,const node&b)
{
if(a.x==b.x) return a.y>b.y;
return a.x<b.x;
}
int main()
{
int n,len,flag,cnt=0;//flag是标记,起点标记1,终点标记0
cin>>n;
for(int i=1;i<=n;i++)
{
long long s,e;
cin>>s>>e;
v.push_back(node(s,1));
v.push_back(node(e,0));
}
sort(v.begin(),v.end(),cmp);
len=v.size();
for(int i=0;i<len;i++)
{
if(i==0)
{
cnt=1;
flag=1;
}
else
{
if(v[i].y==0)
{
if(flag==1)
{
if(v[i].x!=v[i-1].x)
ans[cnt]+=v[i].x-v[i-1].x+1;
else
{
ans[cnt]+=1;
}
}
else
{
if(v[i].x!=v[i-1].x)
ans[cnt]+=v[i].x-v[i-1].x;
}
cnt--;
flag=0;
}
else
{
if(flag==1)
{
if(v[i].x!=v[i-1].x)
ans[cnt]+=v[i].x-v[i-1].x;
}
else
{
if(v[i].x!=v[i-1].x)
ans[cnt]+=v[i].x-v[i-1].x-1;
}
cnt++;
flag=1;
}
}
}
for(int i=1;i<=n;i++)
cout<<ans[i]<<endl;
return 0;
}