?

每个节点维护3个域
A[rt]=2*h[l]+d[l-1]
B[rt]=2*h[l]-d[l-1]
s[rt]=max energy
其中d[l]表示1到l的距离
将环变为线性的1,2…n,1,2…n的2n长度的区间

当一个父亲节点的左右孩子都要查询的时候，s[rt]=max(B[rt<<1]+A[rt<<1|1],max(s[rt<<1],s[rt<<1|1])
否则s[rt]=所查询到的某一边的孩子的s，然后再记录该孩子的A,B值
注意的是u!=v

对于查询，举个例子，要查询区间[3,6]

查询到结点9，没有查询到结点8，所以当前max energy=s[9]=0,记录当前max A=A[9],max B=B[9]
查询到结点5，也查询到结点5，所有当前max energy=max（左孩子的最大，右孩子的最大，跨区间的最大)

语言表达能力好差。。。

217 ms 21900 KB

#include
   
     #define ll long long #define inf (~0ull>>1) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=2e5+10; using namespace std; ll a[maxn<<2],b[maxn<<2],s[maxn<<2]; ll d[maxn],h[maxn]; int n,m; struct node{ ll a,b,mx; node(ll a,ll b,ll mx):a(a),b(b),mx(mx){} }; node null=node(-inf,-inf,0); void push_up(int rt){ a[rt]=max(a[rt<<1],a[rt<<1|1]); b[rt]=max(b[rt<<1],b[rt<<1|1]); s[rt]=max(a[rt<<1]+b[rt<<1|1],max(s[rt<<1],s[rt<<1|1])); } void build(int l,int r,int rt){ if(l==r){ a[rt]=2*h[l]-d[l-1]; b[rt]=2*h[l]+d[l-1]; s[rt]=0; return ; } int m=(l+r)>>1; build(lson); build(rson); push_up(rt); } void _merge(node x,node y,node& z){ z.mx=max(x.mx,y.mx); z.a=max(x.a,y.a); z.b=max(x.b,y.b); z.mx=max(z.mx,x.a+y.b); } node query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R){ node x=node(a[rt],b[rt],s[rt]); return x; } int m=(l+r)>>1; node lx=null,ry=null,res=null; if(L<=m) lx=query(L,R,lson);//左孩子的信息 if(m