P4747 [CERC2017] Intrinsic Interval 解题报告

_XHY20180718_ · 2024-11-17 20:33:46 · 题解

因为没注意到 [l_1,r_1]+[l_2,r_2]=[l_1,r_2]，所以这里是一种线段树维护历史最值的方法。

看到这类型的题，首先有一个结论，一个区间中的数是连续的当且仅当 r-l=\max-\min，根据这个结论，我们可以套路化的用单调栈+扫描线维护 (r-l)-(max-min) 的区间最小值，并且这个值不可能为负数。

具体的，对于每个叶子节点 [i,i]，我们维护当前扫描线扫描到 r，维护 (r-l)+((r-l)-(\max-\min))\times 10^9，其他结点维护区间最小值。

关于维护 \max-\min，可以用单调栈，对于每个最大值相同的区间进行区间加 abs(a_r-a_i)，这样做是 O(n\log n) 的。

我们发现如果这样维护历史最值没什么用，因为线段树保存的是前缀 [1,r] 的，但是我们要找的右端点在右边，考虑从左往右扫一遍（这一遍不维护历史最小值）后再从右往左扫一遍（这一遍仅在扫完 r 时记录历史最小值），从右往左扫的过程便是从左往右的逆过程，我们将第一遍扫描时修改的信息保存下来，在第二次扫描的时候便可以直接用。

那么现在又有一个问题，我们将某个区间进行修改的时候，如果修改值为负数，其历史最值可能会比扫完整个 r 后的历史最值小，所以可以将所有区间加正数提前，区间加负数提后，于是最后扫完 i 其历史最小值就不会收到负数的干扰，于是此题便可以在没有开头提到的性质的情况下做了。

复杂度：O((n+q)\log n)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=1e10;
int n,q,a[N];
int rx,rn,stx[N],stn[N];
struct node{int l,r,k;}ans[N];
vector<node>I[N];
vector<node>qR[N];
struct Segment_Tree{
    #define mid (l+(r-l>>1))
    #define ls (mid<<1)
    #define rs (ls|1)
    struct D{int sw,mn;}tr[N<<1];
    struct M{int fl;}tag[N<<1];
    int L,R,I;M K;
    inline D pushup(D xx,D yy){
        if(xx.mn>yy.mn)swap(xx,yy);
        D res=xx;
        if(xx.mn==yy.mn)res.sw+=yy.sw;
        return res;
    }
    inline D chgD(D xx,M yy,int len){
        xx.mn+=yy.fl;
        return xx;
    }
    inline M chgM(M xx,M yy){
        xx.fl+=yy.fl;
        return xx;
    }
    inline void chg(int id,M fl,int len){
        tr[id]=chgD(tr[id],fl,len);
        tag[id]=chgM(tag[id],fl);
    }
    inline void pushdown(int l,int r,int id){
        if(tag[id].fl){
            chg(ls,tag[id],mid-l+1);
            chg(rs,tag[id],r-mid);
            tag[id].fl=0;
        }
    }
    void build(int l,int r,int id){
        if(l==r){tr[id]={1,l};return;}
        build(l,mid,ls);build(mid+1,r,rs);
        tr[id]=pushup(tr[ls],tr[rs]);
    }
    void upd(int l,int r,int id){
        if(L<=l&&r<=R)return chg(id,K,r-l+1);
        pushdown(l,r,id);
        if(L<=mid)upd(l,mid,ls);
        if(mid<R)upd(mid+1,r,rs);
        tr[id]=pushup(tr[ls],tr[rs]);
    }
    D qry(int l,int r,int id){
        if(l==r)return tr[id];
        pushdown(l,r,id);
        return (I<=mid?qry(l,mid,ls):qry(mid+1,r,rs));
    }
    #undef mid
    #undef ls
    #undef rs
}STR;
#define mid (l+(r-l>>1))
#define ls (mid<<1)
#define rs (ls|1)
struct D{int sm,l,sm_,l_;}tr[N<<1];
struct M{int fm,fm_;}tag[N<<1];
int L,R;M K;
inline D pushup(D xx,D yy){
    D res;
    if(xx.sm>yy.sm)swap(xx,yy);
    res.sm=xx.sm,res.l=xx.l;
    if(xx.sm_>yy.sm_)swap(xx,yy);
    res.sm_=xx.sm_,res.l_=xx.l_;
    return res;
}
inline D chgD(D xx,M yy,int len){
    if(xx.sm_>xx.sm+yy.fm_)xx.l_=xx.l,xx.sm_=xx.sm+yy.fm_;
    if(xx.sm_>xx.sm+yy.fm)xx.l_=xx.l,xx.sm_=xx.sm+yy.fm;
    xx.sm+=yy.fm;
    return xx;
}
inline M chgM(M xx,M yy){
    xx.fm_=min(xx.fm_,xx.fm+yy.fm_);
    xx.fm+=yy.fm;xx.fm_=min(xx.fm_,xx.fm);
    return xx;
}
inline void chg(int id,M fl,int len){
    tr[id]=chgD(tr[id],fl,len);
    tag[id]=chgM(tag[id],fl);
}
inline void pushdown(int l,int r,int id){
    if(tag[id].fm||tag[id].fm_){
        chg(ls,tag[id],mid-l+1);
        chg(rs,tag[id],r-mid);
        tag[id].fm=0;tag[id].fm_=inf;
    }
}
void build(int l,int r,int id){
    if(l==r){STR.I=l;int tt=STR.qry(1,n,1).mn*inf+n-l+1;tr[id]={tt,l,tt,l},tag[id]={0,inf};return;}
    build(l,mid,ls);build(mid+1,r,rs);
    tr[id]=pushup(tr[ls],tr[rs]);
}
void upd(int l,int r,int id){
    if(L<=l&&r<=R)return chg(id,K,r-l+1);
    pushdown(l,r,id);
    if(L<=mid)upd(l,mid,ls);
    if(mid<R)upd(mid+1,r,rs);
    tr[id]=pushup(tr[ls],tr[rs]);
}
D qry(int l,int r,int id){
    if(L<=l&&r<=R)return tr[id];
    pushdown(l,r,id);
    if(L<=mid&&mid<R)return pushup(qry(l,mid,ls),qry(mid+1,r,rs));
    return (L<=mid?qry(l,mid,ls):qry(mid+1,r,rs));
}
#undef mid
#undef ls
#undef rs
signed main(){
    // freopen("std.in","r",stdin);
    // freopen("mine.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;int x,l,r;
    for(int i=1; i<=n; ++i)
        cin>>a[i];cin>>q;
    for(int i=1; i<=q; ++i)
        cin>>l>>r,qR[r].push_back({l,r,i});
    STR.build(1,n,1);
    for(int i=1; i<=n; ++i){
        --STR.tag[1].fl,--STR.tr[1].mn;
        while(rx&&a[stx[rx]]<a[i])
            STR.L=stx[rx-1]+1,STR.R=stx[rx],STR.K={a[i]-a[stx[rx]]},STR.upd(1,n,1),--rx,
            I[i].push_back({STR.L,STR.R,STR.K.fl});
        while(rn&&a[stn[rn]]>a[i])
            STR.L=stn[rn-1]+1,STR.R=stn[rn],STR.K={a[stn[rn]]-a[i]},STR.upd(1,n,1),--rn,
            I[i].push_back({STR.L,STR.R,STR.K.fl});
        stx[++rx]=i,stn[++rn]=i;
    }
    build(1,n,1);
    for(int i=n; i; --i){;
        for(auto j:qR[i]){
            L=1,R=j.l;D tt=qry(1,n,1);
            ans[j.k]={tt.l_,tt.l_+tt.sm_-1,0};
        }
        tag[1].fm+=inf-1,tr[1].sm+=inf-1;
        for(auto j:I[i]){
            L=j.l,R=j.r,K={-j.k*inf,0},upd(1,n,1);
        }
    }
    for(int i=1; i<=q; ++i)
        cout<<ans[i].l<<' '<<ans[i].r<<'\n';
    return 0;
}

另：由于合法区间的可并性质，我们可以直接在扫到 r 的时候找最大的 l，这显然是最优的，然后就不用反着扫了。

代码：

#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define int long long
using namespace std;
const int N=1e5+5,inf=1e10;
int n,q,a[N];
int rx,rn,stx[N],stn[N];
struct node{
    int l,r,k;
    bool operator<(const node &t)
    const {return l<t.l;}
}ans[N];
vector<node>I[N];
vector<node>qR[N];
priority_queue<node>qu;
struct Segment_Tree{
    #define mid (l+(r-l>>1))
    #define ls (mid<<1)
    #define rs (ls|1)
    struct D{int sw,mn,sl;}tr[N<<1];
    struct M{int fl;}tag[N<<1];
    int L,R,I;M K;
    inline D pushup(D xx,D yy){
        if(xx.mn>yy.mn)swap(xx,yy);
        D res=xx;
        if(xx.mn==yy.mn)
            res.sw+=yy.sw;
        res.sl=max(xx.sl,yy.sl);
        return res;
    }
    inline D chgD(D xx,M yy,int len){
        xx.mn+=yy.fl;
        xx.sl-=yy.fl*inf;
        return xx;
    }
    inline M chgM(M xx,M yy){
        xx.fl+=yy.fl;
        return xx;
    }
    inline void chg(int id,M fl,int len){
        tr[id]=chgD(tr[id],fl,len);
        tag[id]=chgM(tag[id],fl);
    }
    inline void pushdown(int l,int r,int id){
        if(tag[id].fl){
            chg(ls,tag[id],mid-l+1);
            chg(rs,tag[id],r-mid);
            tag[id].fl=0;
        }
    }
    void build(int l,int r,int id){
        if(l==r){tr[id]={1,l,l-l*inf};return;}
        build(l,mid,ls);build(mid+1,r,rs);
        tr[id]=pushup(tr[ls],tr[rs]);
    }
    void upd(int l,int r,int id){
        if(L<=l&&r<=R)return chg(id,K,r-l+1);
        pushdown(l,r,id);
        if(L<=mid)upd(l,mid,ls);
        if(mid<R)upd(mid+1,r,rs);
        tr[id]=pushup(tr[ls],tr[rs]);
    }
    D qry(int l,int r,int id){
        if(L<=l&&r<=R)return tr[id];
        pushdown(l,r,id);
        if(L<=mid&&mid<R)return pushup(qry(l,mid,ls),qry(mid+1,r,rs));
        return (L<=mid?qry(l,mid,ls):qry(mid+1,r,rs));
    }
    #undef mid
    #undef ls
    #undef rs
}STR;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;int x,l,r;
    for(int i=1; i<=n; ++i)
        cin>>a[i];cin>>q;
    for(int i=1; i<=q; ++i)
        cin>>l>>r,qR[r].push_back({l,r,i});
    STR.build(1,n,1);
    for(int i=1; i<=n; ++i){
        --STR.tag[1].fl,--STR.tr[1].mn,STR.tr[1].sl+=inf;
        while(rx&&a[stx[rx]]<a[i])
            STR.L=stx[rx-1]+1,STR.R=stx[rx],STR.K={a[i]-a[stx[rx]]},STR.upd(1,n,1),--rx;
        while(rn&&a[stn[rn]]>a[i])
            STR.L=stn[rn-1]+1,STR.R=stn[rn],STR.K={a[stn[rn]]-a[i]},STR.upd(1,n,1),--rn;
        stx[++rx]=i,stn[++rn]=i;
        for(node j:qR[i])qu.push(j);
        STR.L=1;
        while(!qu.empty()){
            node tt=qu.top();STR.R=tt.l;
            ans[tt.k].l=STR.qry(1,n,1).sl;
            ans[tt.k].r=i;
            if(ans[tt.k].l>0)qu.pop();
            else break;
        }
    }
    for(int i=1; i<=q; ++i)
        cout<<ans[i].l<<' '<<ans[i].r<<'\n';
    return 0;
}