Problem Link

考虑全局询问，取出 $a[1,n]$ 的最大值 $a_k$，那么 $a[l,k-1],a[k+1,r]$ 最终都要合并成若干个 $=a_k$ 的节点，然后再合并成一个。

那么考虑笛卡尔树，$f_u$ 表示 $u$ 子树最少合并成几个 $=a_u$ 的节点，转移就是 $f_u=1+\sum_v\lceil2^{a_v-a_u}f_v\rceil$。

那么区间询问就是两条链上的询问，对于每条链可以直接用线段树维护 $u$ 子树内每个点到 $u$ 链的权值，支持区间加区间除即可，势能分析得到 $\mathcal O(n\log V)$ 的复杂度。

时间复杂度 $\mathcal O(n\log V)$。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5,MAXS=1<<20|5;
int n,q,a[MAXN],st[MAXN][20];
struct Segt {
	int mn[MAXS],mx[MAXS],ad[MAXS],tg[MAXS];
	Segt() { memset(tg,-1,sizeof(tg)); }
	void adt(int p,int k) { mn[p]+=k,mx[p]+=k,ad[p]+=k; }
	void cvt(int p,int k) { ad[p]=0,mn[p]=mx[p]=tg[p]=k; }
	void psu(int p) { mn[p]=min(mn[p<<1],mn[p<<1|1]),mx[p]=max(mx[p<<1],mx[p<<1|1]); }
	void psd(int p) {
		if(~tg[p]) cvt(p<<1,tg[p]),cvt(p<<1|1,tg[p]),tg[p]=-1;
		if(ad[p]) adt(p<<1,ad[p]),adt(p<<1|1,ad[p]),ad[p]=0;
	}
	void add(int ul,int ur,int k,int l=1,int r=n,int p=1) {
		if(ul>ur) return ;
		if(ul<=l&&r<=ur) return adt(p,k);
		int mid=(l+r)>>1; psd(p);
		if(ul<=mid) add(ul,ur,k,l,mid,p<<1);
		if(mid<ur) add(ul,ur,k,mid+1,r,p<<1|1);
		psu(p);
	}
	void upd(int ul,int ur,int k,int l=1,int r=n,int p=1) {
		if(ul>ur||!k) return ;
		if(ul<=l&&r<=ur) {
			if(k>=20) return cvt(p,0);
			if((mn[p]>>k)==(mx[p]>>k)) return cvt(p,mn[p]>>k);
		}
		int mid=(l+r)>>1; psd(p);
		if(ul<=mid) upd(ul,ur,k,l,mid,p<<1);
		if(mid<ur) upd(ul,ur,k,mid+1,r,p<<1|1);
		psu(p);
	}
	int qry(int x,int l=1,int r=n,int p=1) {
		if(l==r) return mn[p];
		int mid=(l+r)>>1; psd(p);
		return x<=mid?qry(x,l,mid,p<<1):qry(x,mid+1,r,p<<1|1);
	}
}	TL,TR;
int bit(int x) { return 1<<x; }
int cmp(int x,int y) { return a[x]>a[y]?x:y; }
int qry(int l,int r) {
	int k=__lg(r-l+1);
	return cmp(st[l][k],st[r-bit(k)+1][k]);
}
int f[MAXN],ls[MAXN],rs[MAXN],ans[MAXN];
vector <array<int,3>> qy[MAXN];
int dfs0(int l,int r) {
	int u=qry(l,r); f[u]=1;
	if(l<u) ls[u]=dfs0(l,u-1),f[u]+=1+((f[ls[u]]-1)>>(a[u]-a[ls[u]]));
	if(u<r) rs[u]=dfs0(u+1,r),f[u]+=1+((f[rs[u]]-1)>>(a[u]-a[rs[u]]));
	return u;
}
void dfs1(int l,int r,int u) {
	if(ls[u]) dfs1(l,u-1,ls[u]);
	if(rs[u]) dfs1(u+1,r,rs[u]);
	if(ls[u]) {
		TL.add(l,u-1,-1),TL.upd(l,u-1,a[u]-a[ls[u]]),TL.add(l,u-1,1);
		TR.add(l,u-1,-1),TR.upd(l,u-1,a[u]-a[ls[u]]),TR.add(l,u-1,1);
	}
	if(rs[u]) {
		TL.add(u+1,r,-1),TL.upd(u+1,r,a[u]-a[rs[u]]),TL.add(u+1,r,1);
		TR.add(u+1,r,-1),TR.upd(u+1,r,a[u]-a[rs[u]]),TR.add(u+1,r,1);
	}
	for(auto o:qy[u]) ans[o[2]]=__lg(TL.qry(o[0])+TR.qry(o[1]))+1+a[u];
	TL.add(l,u,1+(rs[u]?(1+((f[rs[u]]-1)>>(a[u]-a[rs[u]]))):0));
	TR.add(u,r,1+(ls[u]?(1+((f[ls[u]]-1)>>(a[u]-a[ls[u]]))):0));
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>a[i],st[i][0]=i;
	for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
	int rt=dfs0(1,n);
	for(int i=1,l,r;i<=q;++i) cin>>l>>r,qy[qry(l,r)].push_back({l,r,i});
	dfs1(1,n,rt);
	for(int i=1;i<=q;++i) cout<<ans[i]<<"\n";
	return 0;
}