Codeforces Round #613

E：给定n个线段覆盖在数轴上，问随便删除一个，剩下的不连续段数最多是多少

题解：先考虑区间修改，然后每次在n个区间中选择一个，该线段在数轴上删除，统计剩余的覆盖片段数量，时间复杂度是o(n^2*数据结构时间)这里的数据结构可以是并查集，也可以是线段树，明显超时，考虑其他方法，这里考虑类似贪心的做法，排序之后从左往右，ans记录总共线段数量，add_union记录删除时候会增加或者减少的区间数量，取最大值再加上原来ans得到答案

ans的做法是遍历序列，只要没有括号嵌套，说明是一段结束了，ans++

add_union考虑三种情况

情况1：

（1）-1   -2  2   -3  这样嵌套，那么id2的那一段在id1段中，而且id2与id3的那一段分离，所以删除1在这里可以+1区间数

（2）-1   -2   1  -3  这样嵌套，那么id1段与id3段分离，删除id2段可以增加1

注意到括号匹配之后剩下的首元素恰好是最开始入栈的元素，这里用multiset模拟可以查看首元素，修改里面的元素的栈，首元素与后面的比较判断情况1

情况2：

-1    1 这样id1的一段删除之后贡献是-1，直接记录

情况3：

-1   -2   1    2，这里2或者1对总线段数的贡献都是0，没有必要记录，删除id2段剩下id1段，反之亦然

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 400100;

pair a[N];
int add_union[N];

int n,m,k,t,l,r,ans1,ans2;

int main(void){
    cin>>t;
    while(t--){
        int ans = 0;
        cin>>n;
        for(int i = 1;i <= n;i++){
            cin>>l>>r;
            a[i*2-1] = {l,-i};///将左端点排序
            a[i*2] = {r,i};///i是用来匹配
            add_union[i] = 0;
        }
        sort(a+1,a+1+2*n);///端点从大到小，左端点优先
        multisets;///最左侧未匹配左端点所在区间
        for(int i = 1;i <= n*2;i++){///左右端点共2n个点
            if(a[i].second < 0)s.insert(-a[i].second);///左端点存储
            else s.erase(s.find(a[i].second));

            if(!s.size())ans++;///单个区间
            if(s.size()==1 && a[i].second>0 && a[i+1].second < 0 && a[i+1].first  > a[i].first)//[ [ ]  也就是可以多一队，下一个端点为[
                add_union[*s.begin()]++;
            if(s.size()==1 && a[i].second<0 && a[i+1].second>0)//当前[ 下一个端点]，删了就少一队
                add_union[*s.begin()]--;
        }
        int num = -0x3f3f3f3f;
        for(int i = 1;i <= n;i++){
            num = max(num,add_union[i]);
        }
        cout<