P2082 区间覆盖(加强版)

admin

https://www.luogu.org/problem/P2082

题目描述
已知有N个区间，每个区间的范围是[si,ti]，请求出区间覆盖后的总长。

输入格式
N s1 t1 s2 t2 …… sn tn

输出格式
共一行，一个正整数，为覆盖后的区间总长。

输入输出样例
输入
3
1 100000
200001 1000000
100000000 100000001
输出
900002
说明/提示
【数据范围】
对于40%的数据 N≤1000，0<Si<Ti≤10000
对于100%的数据 N≤10^5，0<Si<Ti≤10^17，且为整数

admin

一个很直观的做法是假设每一小段长度为1的线段都有

秀木于林

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. struct Node
   
4. {
   
5.     long long x,y;
   
6. }
   
7. a[100010];
   
8. bool cmp(Node a,Node b)
   
9. {
   
10.     return a.x<b.x;
    
11. }
    
12. int main()
    
13. {
    
14.     long long n,ans;
    
15.     cin>>n;
    
16.     for(int i=1; i<=n; i++)
    
17.     {
    
18.         cin>>a[i].x>>a[i].y;
    
19.     }
    
20.     sort(a+1,a+1+n,cmp);
    
21.     long long l=a[1].x,r=a[1].y;
    
22.     for(int i=2; i<=n; i++)
    
23.     {
    
24.         if(r<a[i].x)
    
25.         {
    
26.             ans+=r-l+1;
    
27.             l=a[i].x;
    
28.             r=a[i].y;
    
29.             continue;
    
30.         }
    
31.         r=max(r,a[i].y);
    
32.     }
    
33.     cout<<ans+r-l+1<<endl;
    
34.     return 0;
    
35. }
    

复制代码

admin

典型的线段覆盖，一般小规模的话类似校门口的数，用布尔数组记录全区间里面的每个点是否被覆盖，然后统计1的个数，但是此题规模很大，必须用区间统计的方法，设全区间为[L R]，每条线段为(li ri)：
1、按区间左端点由小到大排序，左端点相同的话右端点小的话在前（其实左端点相同右端点还小的线段根本没有存在的意义）
2、start=l1,end=r1,从第一条线段开始扫描，
3、若下一下线段的左端点li小于或等于当前的end，并且ri>end，则end=ri，可以理解为接起来成为一条更长的线段，但注意包含现象
4、若下一下线段的左端点li大于当前的end，统计上面的start和end之间的长度加进ans，然后重新回到2进行下一段的统计