2018-team4-modules-可持久化线段树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
struct Node{
    Node *ch[2];
    ll mx,id,lazy;
    void update(){
        mx = max(ch[0]->mx,ch[1]->mx);
        if(mx == ch[0]->mx) id = ch[0]->id;
        if(mx == ch[1]->mx) id = ch[1]->id;
        mx += lazy;
    }
}*null,*root[maxn],*it,mem[maxn*50];
inline void init(){
    it = mem;null = it++;
    null->ch[0] = null->ch[1] = null;
    null->mx = null->id = 0;
    root[0] = null;
}
Node* insert(Node *rt,ll l,ll r,ll L,ll R,ll val){
    Node *p = it++;*p = *rt;
    if(L == R && l == r){
        p->id = l;
    }
    if(L <= l && r <= R){
        p->lazy += val;
        p->mx += val;
        return p;
    }
    ll mid = l+r >> 1;
    if(L <= mid) p->ch[0] = insert(p->ch[0],l,mid,L,R,val);
    if(R >  mid) p->ch[1] = insert(p->ch[1],mid+1,r,L,R,val);
    p->update();return p;
}

typedef pair<ll,ll> pa;
inline pa query(Node *p,ll l,ll r,ll L,ll R){
    if(L <= l && r <= R){
        return make_pair(p->mx,p->id);
    }
    ll mid = l+r >> 1;pa x,y;
    if(R <= mid){
        x = query(p->ch[0],l,mid,L,R);
        x.first += p->lazy;
        return x;
    }
    if(L >  mid){
        y = query(p->ch[1],mid+1,r,L,R);
        y.first += p->lazy;
        return y;
    }
    x = query(p->ch[0],l,mid,L,R);
    y = query(p->ch[1],mid+1,r,L,R);
    x.first += p->lazy;y.first+=p->lazy;
    if(x.first > y.first) return x;
    else return y;
}
}}}

struct Node{
    Node *ch[2];
    ll mx,id,lazy;
    void update(){
        mx = max(ch[0]->mx,ch[1]->mx);
        if(mx == ch[0]->mx) id = ch[0]->id;
        if(mx == ch[1]->mx) id = ch[1]->id;
        mx += lazy;
    }
}*null,*root[maxn],*it,mem[maxn*50];
inline void init(){
    it = mem;null = it++;
    null->ch[0] = null->ch[1] = null;
    null->mx = null->id = 0;
    root[0] = null;
}
Node* insert(Node *rt,ll l,ll r,ll L,ll R,ll val){
    Node *p = it++;*p = *rt;
    if(L == R && l == r){
        p->id = l;
    }
    if(L <= l && r <= R){
        p->lazy += val;
        p->mx += val;
        return p;
    }
    ll mid = l+r >> 1;
    if(L <= mid) p->ch[0] = insert(p->ch[0],l,mid,L,R,val);
    if(R >  mid) p->ch[1] = insert(p->ch[1],mid+1,r,L,R,val);
    p->update();return p;
}
typedef pair<ll,ll> pa;
inline pa query(Node *p,ll l,ll r,ll L,ll R){
    if(L <= l && r <= R){
        return make_pair(p->mx,p->id);
    }
    ll mid = l+r >> 1;pa x,y;
    if(R <= mid){
        x = query(p->ch[0],l,mid,L,R);
        x.first += p->lazy;
        return x;
    }
    if(L >  mid){
        y = query(p->ch[1],mid+1,r,L,R);
        y.first += p->lazy;
        return y;
    }
    x = query(p->ch[0],l,mid,L,R);
    y = query(p->ch[1],mid+1,r,L,R);
    x.first += p->lazy;y.first+=p->lazy;
    if(x.first > y.first) return x;
    else return y;
}