• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

校门外的树？能不能离散化+线段树水过。以上均为废话。

题目大意

已知有 $N$ 个区间，每个区间的范围是 $[s_i,t_i]$，请求出区间覆盖后的总长。

对于 $100 \%$ 的数据 ，$N \le 10^5$，$1 \le s_i < t_i \le 10^{17}$。

思路

首先，总长可以由 $t_i-s_i+1$ 得到，所以好像可以发现 $t_i$ 和 $s_i$ 中间的数没有什么太大的意义，可以先尝试不考虑它们。

那么就要考虑两个左右区间的边框了。由于不同区间的顺序是乱的，能不能让我们把区间排一个序呢？这可以利用类似扫描线的思想，把 $t_i$ 和 $s_i$ 拆成两个数，变成了排 $2\times n$ 个数从小到大排序。那么我们还需要在每一位上记录这是左边还是右边。

之后，比如左左右左右右，中间的四个没有意义。诶，如果把左看成(，右看成)，这不是括号匹配吗。(()())是不是更清楚了。我们用一个类似括号匹配的做法做就行了。之后的看注释。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;
struct node{
    ll type,p;
    bool operator <(const node &K)const{
        return p<K.p;
    }
}a[MAXN];
ll n;
int main(){
    scanf("%lld",&n);
    for (int i = 1; i <=n ; ++i) {
        cin>>a[i*2-1].p>>a[i*2].p;//拆成两个
        a[i*2-1].type=0;
        a[i*2].type=1;
    }
    sort(a+1,a+2*n+1);
    ll start=a[1].p,num=0,ans=0;
    for (int i = 1; i <=2*n ; ++i) {
        if(a[i].type==0){
            num++;//有几个“左括号”
        }else{
            num--;
            if(num==0){
            	//左右都匹配了。（数量平衡）
                ans+=a[i].p-start+1;//那么就是当前右节点的位置到最开始的节点
                start=a[i+1].p;//从下一个位置开始。
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}
复制代码

总结

这种区间问题通常可以将 $l$ 和 $r$ 拆成两个在排序后做计算。当然如果你愿意的话可以无脑离散化+扫描线线段树去做（扫描线好像也需要前面那一步）。