洛谷P1496 火烧赤壁

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cmath>
 5 using namespace std;
 6 const int N=20005;
 7 int n,num[N<<1],cnt;
 8 int diff[N<<1],ans,begin=-1;
 9 struct node{int l,r;}f[N];
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     cin>>n;
14     for(int i=1;i<=n;++i)
15     {
16         cin>>f[i].l>>f[i].r;
17         num[++cnt]=f[i].l,num[++cnt]=f[i].r;
18     }
19     sort(num+1,num+1+cnt);
20     int siz=unique(num+1,num+1+cnt)-num;
21     for(int i=1;i<=n;++i)
22     {
23         int nl=lower_bound(num+1,num+siz,f[i].l)-num,
24         nr=lower_bound(num+1,num+siz,f[i].r)-num;
25         //这里一定能找到相等的数
26         ++diff[nl],--diff[nr];
27         //避免端点计算故不使用--diff[nr+1]
28     }
29     for(int i=1;i<=cnt;++i)
30     {
31         diff[i]+=diff[i-1];
32         if(diff[i]&&begin==-1)begin=i;
33         if(!diff[i]&&begin!=-1)ans+=num[i]-num[begin],begin=-1;
34         //统计部分跟随上一注释处有所变动
35     }   cout << ans;
36     return 0;
37 }