P14255 列车（train） 题解

· · 题解

题意

有一个区间集合，一开始包含所有区间，区间 [l,r] 的权值为 p_r-p_l。每次操作给出 [x,y] 删除所有被 [x,y] 包含的区间，查询包含 [x,y] 的区间的最小权值。

做法

把区间看成平面上的点，横坐标是 l，纵坐标是 r，则问题转化成删除右下角的一块区域，查询左上角一块的最小值。

本题中权值有一个重要性质：每一行从左到右递减，从上到下递减。于是如果一个点右边或下面的点可以取到，那么它就不可能是答案。我们称不能向右或向下移动的点为关键点，则答案一定在关键点处取到。如下图，红色的是删除掉的区间，蓝色的是查询区间，橙色的是关键点。发现关键点只会在删除的矩形的交点处，或查询区域的边界处。

关键点的一个性质：同一行或同一列至多有一个关键点，因为如果有多个则靠上或靠左的都不符合定义。因此我们考虑直接维护关键点，考虑一次删除操作 [x,y] 对关键点的影响，首先会删除这次操作右下方的所有关键点，并插入至多两个关键点，即和横坐标小于 x，纵坐标最大的矩形的交点，以及纵坐标大于 y，横坐标最小的矩形的交点。开两个线段树，下标分别为横/纵坐标，维护删除的区间。发现一共只会插入 O(n) 个，因此删除暴力修改线段树即可。

设询问的区间为 [l,r]，和边界的交点容易处理，只要在维护删除的区间的线段树上区间查询即可。还要查询所有满足 x\leq l 且 y\geq r 的关键点 (x,y) 的最小权值。发现关键点的纵坐标是递增的，因此直接线段树上二分出第一个满足 y\geq r 的 x，再开一个线段树维护权值，查最小值即可。时间复杂度 O(n\log n)。

需要支持查询最值及最值的位置的线段树。

代码

写的不是很好。

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define i128 __int128
#define ALL(x) x.begin(),x.end()
#define popcount(x) __builtin_popcountll(x)
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int INF=1e18;
const int N=100005;
const int MOD1=1e9+7,MOD2=998244353;
const int MOD=MOD1;
int n,m;
int a[N];
struct segtree{
    struct Info{
        int mx,posmx;
        int mn,posmn;
        Info operator + (Info y){
            Info res;
            if(mx>y.mx){
                res.mx=mx;
                res.posmx=posmx;
            }else{
                res.mx=y.mx;
                res.posmx=y.posmx;
            }
            if(mn<y.mn){
                res.mn=mn;
                res.posmn=posmn;
            }else{
                res.mn=y.mn;
                res.posmn=y.posmn;
            }
            return res;
        }
    }tr[4*N];
    void pushup(int p){
        tr[p]=tr[p*2]+tr[p*2+1];
    }
    void build(int p,int l,int r){
        if(l==r){
            tr[p].mn=INF;
            tr[p].mx=-INF;
            tr[p].posmx=tr[p].posmn=l;
            return;
        }
        int mid=(l+r)/2;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        pushup(p);
    }
    Info query(int p,int l,int r,int L,int R){
        if(L>R){
            return {-INF,0,INF,0};
        }
        if(l>=L&&r<=R){
            return tr[p];
        }
        int mid=(l+r)/2;
        if(mid>=L){
            Info res=query(p*2,l,mid,L,R);
            if(mid<R){
                return res+query(p*2+1,mid+1,r,L,R);
            }else{
                return res;
            }
        }else{
            return query(p*2+1,mid+1,r,L,R);
        }
    }
    void modify1(int p,int l,int r,int x){
        if(l==r){
            tr[p].mx=-INF;
            tr[p].mn=INF;
            return;
        }
        int mid=(l+r)/2;
        if(mid>=x)modify1(p*2,l,mid,x);
        else modify1(p*2+1,mid+1,r,x);
        pushup(p);
    }

    void modify2(int p,int l,int r,int x,int c){
        if(l==r){
            tr[p].mx=max(tr[p].mx,c);
            tr[p].mn=min(tr[p].mn,c);
            return;
        }
        int mid=(l+r)/2;
        if(mid>=x)modify2(p*2,l,mid,x,c);
        else modify2(p*2+1,mid+1,r,x,c);
        pushup(p);
    }
    int find(int p,int l,int r,int x){
        if(l==r){
            return (tr[p].mx>=x?l:-1);
        }
        int mid=(l+r)/2;
        if(tr[p*2].mx>=x){
            return find(p*2,l,mid,x);
        }else{
            return find(p*2+1,mid+1,r,x);
        }
    }
}T1,T2,T3,T4,T5;
//T1 T2维护直接走 T1下标l T2下标r
//T3 T4维护关键点位置 T3下标l T4下标r
//T5维护关键点权值
void solve_(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    T1.build(1,1,n);
    T2.build(1,1,n);
    T3.build(1,1,n);
    T4.build(1,1,n);
    T5.build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){

            while(1){
                segtree::Info pos=T3.query(1,1,n,l,n);
                if(pos.mn<=r){
                    T3.modify1(1,1,n,pos.posmn);
                    T4.modify1(1,1,n,pos.mn);
                    T5.modify1(1,1,n,pos.posmn);
                }else{
                    break;
                }
            }
            T1.modify2(1,1,n,l,r);
            T2.modify2(1,1,n,r,l);
            segtree::Info pos=T1.query(1,1,n,1,l-1);
            if(pos.mx<r&&pos.mx!=-INF){
                //l-1 r+1
                //debug(pos.mx+1,l-1);
                int w=a[pos.mx+1]-a[l-1];
                T3.modify2(1,1,n,l-1,pos.mx+1);
                T4.modify2(1,1,n,pos.mx+1,l-1);
                T5.modify2(1,1,n,l-1,w);
            }

            pos=T2.query(1,1,n,r+1,n);
            if(pos.mn>l&&pos.mn!=INF){
                //debug(pos.mn);
                int w=a[r+1]-a[pos.mn-1];
                T3.modify2(1,1,n,pos.mn-1,r+1);
                T4.modify2(1,1,n,r+1,pos.mn-1);
                T5.modify2(1,1,n,pos.mn-1,w);
            }

        }else{
            int ans=INF;
            segtree::Info mxr=T1.query(1,1,n,1,l);
            segtree::Info mnl=T2.query(1,1,n,r,n);
            //debug(mxr.mx,mnl.mn);
            if(mxr.mx<r){
                ans=min(ans,a[r]-a[l]);
            }else{
                if(mxr.mx+1<=n){
                    ans=min(ans,a[mxr.mx+1]-a[l]);
                }
            }
            if(mnl.mn>l){
                ans=min(ans,a[r]-a[l]);
            }else{
                if(mnl.mn-1>=1){
                    ans=min(ans,a[r]-a[mnl.mn-1]);
                }
            }
            // if(l==68&&r==83){
            //     debug(ans);
            // }
            int res=T3.find(1,1,n,r);
            if(res!=-1&&res<=l){
                ans=min(ans,T5.query(1,1,n,res,l).mn);
            }
            if(ans==INF){
                cout<<"-1\n";
                continue;
            }
            cout<<ans<<"\n";
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase,multitest=1;
    if(multitest)cin>>testcase;
    else testcase=1;
    while(testcase--){
        solve_();
    }
    return 0;
}