自动搬运

查看原文

来自洛谷，原作者为

	min_inf 你路过的 与我追逐的 我会等它们重合

搬运于2025-08-24 23:15:32，当前版本为作者最后更新于2025-05-23 16:35:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $b_i=\max(a_i,a_{i+1})$，考虑在 $b$ 上操作，每次操作就是删掉一个数 $x$ 并且两侧都对 $x+1$ 取 $\max$。然后肯定是删最小的影响最小，考虑一个长度为 $l$ 的最小值 $x$ 的连续段，至少会操作出 $\lfloor \frac l 2 \rfloor$ 个 $x+1$。然后单次询问就可以直接在笛卡尔树上 DP 了。

考虑怎么刻画一个区间的笛卡尔树，找到最大值，然后就是最大值左侧所有前缀 $\max$（单调栈上的树）的右子树和右侧所有后缀 $\max$ 的左子树。

然后我们要在维护单调栈的同时维护笛卡尔树上的 DP 值。假如没有相同的数，我们暴力往上跳直到 DP 值没有变化，由于修改一定是增加，经过 $\log n$ 次后是一串 $+1$，经过的都是奇数变成偶数，而每次只会增加 $\log n$ 的势能，时间复杂度就是 $O(n\log n)$ 的。

考虑有相同的数的情况，我们建两棵笛卡尔树，分别认为相同的数左侧/右侧大，解决第一个最大值左侧和最后一个最大值右侧的情况，中间的部分可以在随便一棵树上前缀和一下。时间复杂度 $O((n+q)\log n)$。

#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second

constexpr int N = 3e5+5;
constexpr int S(int x,int y){return y<32?x>>y:0;}

int n,m;
int a[N],b[N];
int ls[N],rs[N],f[N];
void dfs1(int u){
    if(!u)return;
    dfs1(ls[u]),dfs1(rs[u]);
    f[u]=S(f[ls[u]],a[u]-a[ls[u]])+S(f[rs[u]],a[u]-a[rs[u]])+1;
}
int L(int u){return S(f[ls[u]],a[u]-a[ls[u]])+1;}
int R(int u){return S(f[rs[u]],a[u]-a[rs[u]])+1;}

int stk[N],tp,fs[N];
int sl[N];
void dfs2(int u,int fa){
    if(!u)return;
    sl[u]=sl[fa]+L(u);
    dfs2(ls[u],u),dfs2(rs[u],u);
}

int ans[N],cnt[N];
vector<pair<int,int>> Ql[N],Qr[N];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    cin>>n>>m;rep(i,1,n)cin>>b[i];
    rep(i,1,n-1)a[i]=max(b[i],b[i+1]);--n;
    rep(i,1,m){
        int l,r;cin>>l>>r;
        if(l==r)ans[i]=b[l];
        else{
            --r;
            Ql[l].emplace_back(r,i);
            Qr[r].emplace_back(l,i);
        }
    }
    rep(i,1,n){
        int lst=0;while(tp&&a[stk[tp]]<a[i])lst=stk[tp--];
        rs[stk[tp]]=i,ls[stk[++tp]=i]=lst;
    }dfs1(rs[0]),dfs2(rs[0],0);
    tp=0;per(i,n,1){
        while(tp&&a[stk[tp]]<=a[i])--tp;
        stk[++tp]=i;fs[tp]=R(i);
        int p=tp;while(p>1){
            int w=R(stk[p-1])+S(fs[p],a[stk[p-1]]-a[stk[p]]);
            if(w!=fs[p-1])fs[--p]=w;else break;
        }
        for(auto [r,id]:Ql[i]){
            p=lower_bound(stk+1,stk+tp+1,r,greater<int>())-stk;
            cnt[id]=-sl[stk[p]],ans[id]=a[stk[p]];
            if(p<tp)cnt[id]+=S(fs[p+1],a[stk[p]]-a[stk[p+1]]);
        }
    }
    rep(i,1,n)ls[i]=rs[i]=0;tp=0;
    rep(i,1,n){
        int lst=0;while(tp&&a[stk[tp]]<=a[i])lst=stk[tp--];
        rs[stk[tp]]=i,ls[stk[++tp]=i]=lst;
    }dfs1(rs[0]);
    tp=0;rep(i,1,n){
        while(tp&&a[stk[tp]]<=a[i])--tp;
        stk[++tp]=i;fs[tp]=L(i);
        int p=tp;while(p>1){
            int w=L(stk[p-1])+S(fs[p],a[stk[p-1]]-a[stk[p]]);
            if(w!=fs[p-1])fs[--p]=w;else break;
        }
        for(auto [l,id]:Qr[i]){
            p=lower_bound(stk+1,stk+tp+1,l)-stk;
            cnt[id]+=sl[stk[p]]+1;
            if(p<tp)cnt[id]+=S(fs[p+1],a[stk[p]]-a[stk[p+1]]);
        }
    }
    rep(i,1,m)cout<<ans[i]+(cnt[i]?__lg(cnt[i])+1:0)<<'\n';
}