题解 P2082 【区间覆盖(加强版)】

· · 题解

Updated at 2024.2.2：针对题解区的 Hack 进行了修改。

粗看一眼题目，咦，这不是校门外的树吗？

再看一眼题目，咦，我不是出过一道一模一样的题吗？

啊哈哈，双倍经验！！！

考虑括号匹配的过程。

每一个区间都是一对括号。例如 [1,5] 这个区间，就是在数轴上 1 的位置放上左括号，5 的位置放上右括号。

那么，哪些位置是被覆盖的呢？显然，如果一个点被至少一对括号经过，这个点就是被覆盖的。被几对括号经过，就是被几次覆盖的。

For Example（来自P1047）：

3
150 300
100 200
470 471
-------100----150---200-----300--------470--471--
--------(------(-----)-------)----------(----)---
00000000(111111(22222)1111111)0000000000(1111)000

我们惊喜地发现，这就是一个括弧匹配问题！！！

我们用一个变量表示左括号个数，我们不停地为第一个左括号找到匹配的右括号，并加上这一段的总长度。

这时候我们要考虑一个细节——对于坐标相同的左右括号，我们应该把谁放在前面呢？

如果是严格地求线段长度其实是无所谓的——不管你把一条线段从共有部分断开还是不断开，答案都是 r-l——但是这里不一样，当左右端点重合时，答案线段必须不断开。

#include <bits/stdc++.h>
using namespace std;
struct p1047//没错，一开始只是想写一个校门外的树plus
{
    long long num;
    bool t;//0表示这是一个左括号，1表示右括号
}p,a[200005];
bool cmp(p1047 x,p1047 y)
{
    if(x.num==y.num)
        return x.t<y.t;
    return x.num<y.num;
}
int main()
{
    int m,x;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&a[i*2-1].num,&a[i*2].num);
        //每个区间由一个左括号和一个右括号组成
        a[i*2-1].t=0;
        a[i*2].t=1;
    }
    sort(a+1,a+m*2+1,cmp);//对所有括号排序
    long long st=a[1].num;//第一个左括号
    int cs=1;//剩余括号数量
    long long tot=0;//总长度
    for(int i=2;i<=m*2;i++)
    {
        if(a[i].t==0)//左括号
            cs++;
        else//右括号
            cs--;
        if(cs==0)//一段区间结束，结算
        {
            tot+=a[i].num-st+1;
            st=a[i+1].num;
            //加入下一个左括号
        }
    }
    cout<<tot;
    return 0;
}