出题人题解 | #little w and Segment Coverage#

原题解链接：https://ac.nowcoder.com/discuss/150260

可以线段树,但是没必要。因为是先给出线段最后在做询问,所以可以用差分区间修改,最后来一遍前缀和还原。

然后记录数组中被线段仅仅覆盖1次的位置,将这些位置的权值标为1 ,做一遍前缀和。

然后答案就是$sum[r]-sum[l-1]sum[r]-sum[l-1]$这样,注意再加上一开始就没有被线段覆盖的点就好了。

#include<bits/stdc++.h>

using namespace std;
int n,m;
const int N = 1e5+5;
int a[N];
long long b[N];
int buc[N];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) {
        int l,r;
        scanf("%d%d", &l, &r);
        a[l]++; a[r+1]--;
        b[l]+=i; b[r+1]-=i;
    }
    for(int i=1;i<=n;++i) a[i]+=a[i-1], b[i]+=b[i-1];
    int tmp=0;
    for(int i=1;i<=n;++i) {
        if(a[i]==1) { 
            buc[ b[i] ] ++;
        }
        if(a[i]==0) tmp++;
    }
    int mi=1e6, ans=0;
    for(int i=m;i>=1;--i) {
        if(buc[i] < mi) ans = i, mi = buc[i];
    }
    printf("%d %d\n", ans,mi+tmp);    
    
    return 0;
}