Codeforces Round #292 (Div. 2)E. Drazil and Park——線段樹

Codeforces Round #292 (Div. 2)E. Drazil and Park——線段樹

每個節點維護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