rt,笛卡尔树不带优化的分治,过程中求解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7,LogN=20;
inline int qpow(int a,int b)
{
	int ans=1,base=a;
	while(b)
	{
		if(b&1)
		{
			ans*=base;
			ans%=mod;
		}
		base*=base;
		base%=mod;
		b>>=1;
	}
	return ans;
}
int n,h[N],st[N][LogN],f[10],g[10],Log[N];
inline int query(int x,int y)
{
	int l=Log[y-x+1];
	int t1=st[x][l],t2=st[y-(1<<l)+1][l];
	return h[t1]<=h[t2]?t1:t2;
}
inline int solve(int l,int r,int h0)
{
	if(l>=r)
	{
		g[l]=h[l]-h0;
		return l;
	}
	int p=query(l,r);
	int lcp=solve(l,p-1,h[p]);
	int rcp=solve(p+1,r,h[p]);
	g[p]=g[lcp]+g[rcp]+h[p]-h0;
	f[p]=((((2*((f[lcp]+qpow(2,g[lcp]))%mod))%mod)*((f[rcp]+qpow(2,g[rcp]))%mod))%mod-qpow(2,g[lcp]+g[rcp]+1)+mod+qpow(2,g[p]))%mod;
	return p;
}
int main()
{
	clock_t c1=clock();
#ifdef LOCAL
 	freopen("1.in","r",stdin);
 	freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
		st[i][0]=i;
	}
	Log[1]=0;
	for(int i=2;i<=N-5;i++)Log[i]=Log[i>>1]+1;
	for(int j=1;j<=Log[n];j++)
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			int t1=st[i][j-1],t2=st[i+(1<<j-1)][j-1];
			if(h[t1]<=h[t2])
				st[i][j]=t1;
			else
				st[i][j]=t2;
		}
	}
	cout<<f[solve(1,n,0)];
#ifdef LOCAL
	cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
 	return 0;
}