题解：P6645 [CCO 2020] Interval Collection

· · 题解

本题思路：

这道题我们其实本质上是求线段的交集最小的两条的左右端点之差(如果选择多条可能使答案更劣，因为多条的公共部分一定可以表示为其中的两条相交)，那么明显如果有两条线段没有交集那么一定是最优的，否则最小交的部分一定是 l 的最大值与 r 的最小值框出的一部分（如果有不交的情况 l 就会小于 r，否则一定有交）。

先考虑有两条线段不相交的情况，那么我们可以在以最大的 l 为左端点的线段中选择一个最小的 r，在最小的以 r 为右端点的 l，两者相减即可。

然后就考虑有线段无交的情况，那么线段无交的充要条件是一条线段的左端点大于另一条线段的右端点或这条线段的右端点小于另一条的左端点。在满足这个条件后我们希望左端点越大越好，右端点越小越好。这就可以发现其实如果确定了区间答案的大小范围，区间价值是可以合并的。考虑线段树，在每个子节点上记录以当前位置为左端点的最小右端点和以当前位置为右端点的最大左端点，删除加入可以用平衡树或者 set 维护。而上传就简单了，因为区间的值是从小到大，左子树内为右端点的线段与右子树内为左端点的线段就不交，直接维护一个答案最小值即可。

本题代码：

#include<bits/stdc++.h>
#define ls t[p].ch[0]
#define rs t[p].ch[1]
#define mid (tr[p].l+tr[p].r)/2
using namespace std;
int root[1000005][2];
struct f{int l,r,ans,sum[2];}tr[1000005*4];
struct ff{char a;int x,y;}b[500005];
struct f1{int ch[2],rnd,sum,ma,mi;}t[1000005];
void wei(int p){
    tr[p].sum[0]=max(tr[p*2].sum[0],tr[p*2+1].sum[0]);
    tr[p].sum[1]=min(tr[p*2].sum[1],tr[p*2+1].sum[1]);
    tr[p].ans=min(tr[p*2].ans,tr[p*2+1].ans);
    tr[p].ans=min((long long)tr[p].ans,(long long)tr[p*2+1].sum[1]-tr[p*2].sum[0]+1);
}
void jianshu(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].sum[0]=t[root[tr[p].l][0]].ma;
        tr[p].sum[1]=t[root[tr[p].l][1]].mi;
        tr[p].ans=INT_MAX;return;
    }
    jianshu(p*2,l,mid),jianshu(p*2+1,mid+1,r);
    wei(p);
}
void wei1(int p){
    t[p].ma=max(t[ls].ma,max(t[rs].ma,t[p].sum));
    t[p].mi=min(t[ls].mi,min(t[rs].mi,t[p].sum));
}
void split(int p,int &x,int &y,int k){
    if(!p){x=y=0;return;}
    if(t[p].sum<=k) x=p,split(rs,rs,y,k),wei1(x);
    else y=p,split(ls,x,ls,k),wei1(y);
}
void merge(int &p,int x,int y){
    if(!x||!y){p=x+y;return;}
    if(t[x].rnd<=t[y].rnd) p=x,merge(rs,rs,y);
    else p=y,merge(ls,x,ls);
    wei1(p);
}
int cnt;
int add(int p){t[++cnt].sum=p;t[cnt].ma=t[cnt].mi=p;t[cnt].rnd=rand();return cnt;}
void xiugai(int p,int l,int k,int pd){
    if(tr[p].l==tr[p].r){
        if(pd==1){
            int x,y;split(root[tr[p].l][0],x,y,k);
            merge(x,x,add(k));merge(root[tr[p].l][0],x,y); 
        }
        if(pd==2){
            int x,y,z;split(root[tr[p].l][0],x,y,k);
            split(x,x,z,k-1);merge(z,t[z].ch[0],t[z].ch[1]);
            merge(x,x,z),merge(root[tr[p].l][0],x,y);
        }
        if(pd==3){
            int x,y;split(root[tr[p].l][1],x,y,k);
            merge(x,x,add(k));merge(root[tr[p].l][1],x,y); 
        }
        if(pd==4){
            int x,y,z;split(root[tr[p].l][1],x,y,k);
            split(x,x,z,k-1);merge(z,t[z].ch[0],t[z].ch[1]);
            merge(x,x,z),merge(root[tr[p].l][1],x,y);
        }
        tr[p].sum[0]=t[root[tr[p].l][0]].ma;
        tr[p].sum[1]=t[root[tr[p].l][1]].mi;
        tr[p].ans=INT_MAX;
        return;
    }
    if(l<=mid) xiugai(p*2,l,k,pd);
    else xiugai(p*2+1,l,k,pd);
    wei(p);
}
int cha(int p,int l,int pd){
    if(pd==0){return t[root[l][1]].mi;}
    return t[root[l][0]].ma;
}
signed main(){
    t[0].mi=INT_MAX,t[0].ma=-INT_MAX;
    int q;cin>>q;
    jianshu(1,1,1000000);
    while(q--){
        char op;int l,r;cin>>op>>l>>r;r--;
        if(op=='A'){xiugai(1,r,l,1);xiugai(1,l,r,3);}
        else{xiugai(1,r,l,2),xiugai(1,l,r,4);}
        if(tr[1].sum[0]<=tr[1].sum[1]){
            cout<<cha(1,tr[1].sum[0],0)-cha(1,tr[1].sum[1],1)+1<<'\n';
        }
        else cout<<tr[1].ans<<'\n';
    }
    return 0;
}