洛谷 P8037 题解

· · 题解

洛谷 P8037 题解

\text{Link}

思路分析

好题，考虑对询问离线并按右端点排序

我们先考虑右端点是最大值的情况，反过来的只需要对每个数取反再做一次

记录每个点为区间左端点能够达到最远的右端点

考虑加入新的一个点 a_r，那么我们需要更新某一段区间 [l,r] 中的数的右端点为 r，其中 l 为满足 l\le r 且 a_{l-1}>a_r 的最大整数

为了快速求出 l，我们可以维护一个递减的单调栈

接下来考虑 [l,r] 区间内有哪些点的右端点可以被更新为 r，假设某个点 a_x 的右端点可以被更新为 r，当且仅当：

\forall k\in[x,r],a_k\ge a_x

那么如果加入 a_r，每一个满足 a_x> a_r 的点以后就一直不能被更新了，所以我们再维护一个递增的单调栈，每次弹栈弹掉的这些元素就不能再更新右端点

考虑对以上操作用线段树维护以下信息：

注意那些不能更新右端点的点依然可能对答案做出贡献

时间复杂度 \Theta(n\log n)

总结：

离线按右端点排序是处理区间问题的一个常用 trick（就是不知道本题强制在线怎么做。。。）

把所有数取反再跑一遍的 trick 看起来好像也还挺高妙的

有些区间问题可以固定右端点然后考虑左端点的贡献，这个做法好像我还没见过

一些实现的细节请看代码

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
int n,m;
class SegmentTree {
    private:
        struct node {
            int pos,len,tag;
            /*
             * pos: 当前最左合法左端点 
             * len: 当前区间最大长度
             * tag: 区间更新右端点的懒标记 
             */
        }   tree[MAXN<<2];
        inline int left(int x) {
            return x<<1;
        }
        inline int right(int x) {
            return x<<1|1;
        }
        inline void pushup(int pos) {
            tree[pos].len=max(tree[left(pos)].len,tree[right(pos)].len);
            tree[pos].pos=(!tree[left(pos)].pos)?tree[right(pos)].pos:tree[left(pos)].pos;
        }
        inline void pushdown(int pos) {
            //用pos作为右端点更新两个区间的最大长度 
            if(!tree[pos].tag) return ;
            tree[left(pos)].tag=max(tree[left(pos)].tag,tree[pos].tag);
            tree[right(pos)].tag=max(tree[right(pos)].tag,tree[pos].tag);
            if(tree[left(pos)].pos) {
                tree[left(pos)].len=max(tree[left(pos)].len,tree[pos].tag-tree[left(pos)].pos+1);
            }
            if(tree[right(pos)].pos) {
                tree[right(pos)].len=max(tree[right(pos)].len,tree[pos].tag-tree[right(pos)].pos+1);
            }
            tree[pos].tag=0;
        }
    public:
        inline void Build(int l=1,int r=n,int pos=1) {
            if(l==r) {
                tree[pos].pos=tree[pos].len=tree[pos].tag=0;
                return ;
            }
            int mid=(l+r)>>1;
            Build(l,mid,left(pos));
            Build(mid+1,r,right(pos));
            pushup(pos);
        }   
        inline void ModifyL(int u,int k,int l=1,int r=n,int pos=1) {
            //修改左端点是否合法 
            if(l==r) {
                tree[pos].pos=k;
                return ;
            }
            pushdown(pos);
            int mid=(l+r)>>1;
            if(u<=mid) ModifyL(u,k,l,mid,left(pos));
            else ModifyL(u,k,mid+1,r,right(pos));
            pushup(pos);
        }
        inline void ModifyR(int ul,int ur,int k,int l=1,int r=n,int pos=1) {
            //区间修改右端点 
            if(ul<=l&&r<=ur) {
                if(tree[pos].pos) tree[pos].len=max(tree[pos].len,k-tree[pos].pos+1);
                tree[pos].tag=max(tree[pos].tag,k);
                return ;
            }
            pushdown(pos);
            int mid=(l+r)>>1;
            if(ul<=mid) ModifyR(ul,ur,k,l,mid,left(pos));
            if(mid<ur) ModifyR(ul,ur,k,mid+1,r,right(pos));
            pushup(pos);
        }
        inline int Query(int ql,int qr,int l=1,int r=n,int pos=1) {
            if(ql<=l&&r<=qr) return tree[pos].len;
            pushdown(pos);
            int mid=(l+r)>>1,res=0;
            if(ql<=mid) res=max(res,Query(ql,qr,l,mid,left(pos)));
            if(mid<qr) res=max(res,Query(ql,qr,mid+1,r,right(pos)));
            return res;
        }
}   S;
struct query {
    int l,id;
};
vector <query> q[MAXN];
int st1[MAXN],st2[MAXN],a[MAXN],ans[MAXN];
inline void solve() {
    st1[0]=st2[0]=0; //单调栈栈顶 
    S.Build();
    for(int i=1;i<=n;++i) {
        while(st1[0]&&a[st1[st1[0]]]<=a[i]) --st1[0];
        int l=st1[st1[0]]+1;
        st1[++st1[0]]=i;
        while(st2[0]&&a[st2[st2[0]]]>a[i]) {
            S.ModifyL(st2[st2[0]],0);
            //这个点以后都不能更新新的右端点了 
            --st2[0];
        }
        st2[++st2[0]]=i;
        S.ModifyL(i,i);
        S.ModifyR(l,i,i);
        for(auto qry:q[i]) {
            ans[qry.id]=max(ans[qry.id],S.Query(qry.l,i));
        }
    }
}
signed main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;++i) {
        int l,r;
        scanf("%d%d",&l,&r);
        q[r].push_back((query){l,i});
    }
    solve();
    for(int i=1;i<=n;++i) a[i]*=-1;
    solve();
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}