区间合并

这个算法很难，其实我也不太理解（真的）。
区间和并的算法就是将多个区间合并成最少的区间。
请看题目：ACWING.803区间合并
本题就是区间合并的一个应用。
接下来大家想一想怎么合并区间。

好，大家想明白了请看后面。
本题可以使用一点分治的思路。

分治就是把一个大问题分成许多小问题。——是谁说的我忘了（逃

于是我们可以把整个情况分为三个小的情况。
分别是：

• 情况1：一个区间包含另一个区间。
• 情况2：一个区间的一部分在一个区间，其他不在。
• 情况3：两个区间没有交集。

具体我们看一下图。

好接下来我们分别对三种情况进行讨论。

首先是第一种
我们把res更新成大的那个区间。

第二种
我们把res的左端点更新为左端点更小的区间的左端点，右端点更新为右端点更大的区间的右端点。
这局话可能大家读起来有点晕。
其实很简单，说人话就是把绿色区间的右端点变成红色区间的右端点（见上图）。

第三种
我们啥也不管。

好接下来我们看看合并的过程。
这里为了方便敲代码我们简单介绍一下pair。
pair是一个STL，它可以同时存储两个相邻的元素。
具体定义方法如下：

pair<int, int> q;//定义一个整形的pair
int x = q.first;//取q数对的第一个数。注意不用加括号
int y = q.second;//取q数对的第二个数。

当然pair还有一个黑科技就是能储存三元组。
具体方法如下：

pair<int, pair<int, int>> q;
int a = q.first//三元组q的第一个数
//好戏在这里，请准备好

//准备好请继续看

int b = q.second.first;//三元组q的第二个数
int c = q.second.second;//三元组q的第三个数。

当然你也可以用这种方法写n元组。
代码环节：

#include<bits/stdc++.h>
using namespace std;
#define v vector<pair<int, int>>
v segs;
void m(v &segs)
{
    v res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for(auto seg : segs)
    {
        if(ed < seg.first)
        {
            if(st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }
    if(st != -2e9) res.push_back({st, ed});
    segs = res;
}
int main()
{
    int n;cin>>n;
    for(int i = 0;  i< n; i ++)
    {
        int l,r;cin>>l >> r;
        segs.push_back({l,r});
    }
    m(segs);
    cout<<segs.size();
}

今天的分享就到这里了，下午更新大家的噩梦KMP。

（这里要感谢抽风大佬，0凌大佬和季科大佬帮助本蒟蒻理解KMP。）
点击这里查看cht的全部分享

下期见，bye！