线段覆盖（题解）

小半 • 2023年2月15日上午10:12 • 软件工程 • 阅读 112

原题

题目描述

有一段道路，长度为1e18，现在有n个人对其进行刷漆,每个人会随意选取一段道路进行刷漆，每个人会从li刷到ri,包含li和ri
求被刷了k次的道路的段数，k∈[1,n]

输入

第一行一个整数n，1<=n<=2e5;
接下来n行，每行一两个整数，l,r。0<=l<=r<=1e18;

输出

n个整数，用空格隔开，分别表示被刷i次的路段的个数。1<=i<=n;

样例输入

样例输出

3 2 2 2

提示

被刷1次的 0,7,8
被刷2次的 1,6
被刷3次的 2,5
被刷4次的 3,4

AC代码

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 2*100000+10;
int n;
typedef struct load{
    ll num;
    int f;
}load;
load a[N*2];
ll b[N+10];
bool comp(load a,load b){
    return a.num<b.num;
}

int main(){
    cin>>n;
    ll l,r;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        a[i].num = l;
        a[n+i].num = r+1;
        a[i].f = 1;
        a[n+i].f = -1;
    }
    sort(a,a+2*n,comp);
    int cur = 1;
    for(int i=0;i<n*2-1;i++){
        b[cur]+=a[i+1].num-a[i].num;
        cur+=a[i+1].f;
    }
    for(int i=1;i<n+1;i++){
        cout<<b[i]<<' ';
    }
    cout<<endl;
    return 0;
}

解释

1、a[n+i].num = r+1，为什么要加一？

答：因为从l到r都加一，则应加的应该是l-r+1，加一则可直接得l+1-r。

2、结构体中得f是啥意思？

答：输入时的l和r，输入l时，f为1，输入r时，f为-1。

3、变量cur是啥意思？

答：cur等于几，则是计算到现在的刷了几遍的路。

4、cur有啥用？

答：cur联合f就可以实现对刷了几遍的进行改变，方便进行多次统计。

5、f有啥用？

答：便于语句cur+=a[i+1].f实现功能。

6、b数组有啥用？

答：用来记录被刷了i遍的路段数。

注意

前边和后边的0不能忘了。

扩展题

题目改成：输出各段路（从0到n（1e18减少到1e9））被刷了几次。

参考代码

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int N = 2*100000+10;
int n;
typedef struct load{
    ll num;
    int f;
}load;
load a[N*2];
bool comp(load a,load b){
    return a.num<b.num;
}

int main(){
    cin>>n;
    ll l,r;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        a[i].num = l;
        a[n+i].num = r+1;
        a[i].f = 1;
        a[n+i].f = -1;
    }
    sort(a,a+2*n,comp);
    int cur = 1;
    for(int i=0;i<n*2-1;i++){
        for(int j=0;j<a[i+1].num-a[i].num;j++){
            cout<<cur<<' ';
        }

        cur+=a[i+1].f;
    }
    return 0;
}