F. Multi-Colored Segments

洛谷最优解

显然我们对于每一个线段可以分成左右两端考虑
我们先按照l sort一遍
然后每次计算与他最近的值
我们维护两个最大的r即可
然后每次更新
然后我们再倒着做一遍
对于每一个r 找到最近的l
然后每次更新l
我们l要记录次大和最大 因为颜色只有相同和不同两种
最后输出答案的时候取min即可
其实这里的证明并不明朗
本来我是想反着的时候还应该sort一遍的
但是比不sort更错了
我就直接交了个不sort的 居然过了 还跑的飞快

void solve(){
    int n;cin>>n;
    vector<tuple<int,int,int,int>>v;
    for(int i=1;i<=n;i++){
        int l,r,c;cin>>l>>r>>c;
        v.push_back({l,r,c,i-1});
    }
    sort(all(v));
    int r1=-INF+1,c1=n+1,r2=-INF,c2=n+2;//r1最近 r2次近
    vector<int>a(n),b(n);
    for(int i=0;i<n;i++){
        auto [l,r,c,pos]=v[i];
        if(c1!=c){
            a[pos]=l-r1;
        }else{
            a[pos]=l-r2;
        }
        //gengxin
        if(c==c1||c==c2){
            if(c==c1){
                r1=max(r1,r);
            }else{
                r2=max(r2,r);
            }
            if(r2>r1){
                swap(r1,r2);
                swap(c1,c2);
            }
        }else{
            if(r>r2){
                r2=r;
                c2=c;
            }
            if(r2>r1){
                swap(r1,r2);
                swap(c1,c2);
            }
        }
    }
    int l1=INF,l2=INF+1;
    c1=n+1,c2=n+2;
    //sort(all(v),cmp);
    for(int i=n-1;i>=0;i--){
        auto [l,r,c,pos]=v[i];
        if(c1!=c){
            b[pos]=l1-r;
        }else{
            b[pos]=l2-r;
        }
        if(c==c1||c==c2){
            if(c==c1){
                l1=min(l1,l);
            }else{
                l2=min(l2,l);
            }
            if(l2<l1){
                swap(l1,l2);
                swap(c1,c2);
            }
        }else{
            if(l<l2){
                l2=l;
                c2=c;
            }
            if(l2<l1){
                swap(l1,l2);
                swap(c1,c2);
            }
        }
    }
    for(int i=0;i<n;i++)cout<<max(0ll,min(a[i],b[i]))<<' ';cout<<endl;
}