题解：P12430 [BalticOI 2025] Exponents

· · 题解

设 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';
}