线段树动态开点区间加区间求和

线段树动态开点区间加区间求和

---

题目来源：

陕西师范大学第七届程序设计竞赛网络同步赛 H. 万恶的柯怡

思想：

保证叶子节点被完整的覆盖，需要开节点，就把左右儿子都开出来，其余和普通线段树一样。

tips：

用结构体内部函数，内存不足，（第一次遇见本地问题不严重）不明嚼栗？？？

模板：

#include <bits/stdc++.h>
typedef long long ll;
const int N = 4000010;
using namespace std;
struct node{
    ll sum,tag;int lson,rson;
//    node(){}node(ll c,ll d,int e,int f){ ***memory limit error***
//        sum=c;tag=d;lson=e;rson=f;
//    }
}T[N];
int cnt;
void newnode(int &x,ll sum) {
    x = ++cnt;
    T[x].sum = sum;
    T[x].lson = T[x].rson = -1;
    T[x].tag = 0;
}
void push_down(int p,ll l,ll r) {
    ll mid = (l+r) >> 1LL;
    if(T[p].tag) {
        if(T[p].lson==-1&&T[p].rson==-1){
            newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
            newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
            T[T[p].lson].tag += T[p].tag;
            T[T[p].rson].tag += T[p].tag;
        }
        else {
            T[T[p].lson].tag += T[p].tag;
            T[T[p].rson].tag += T[p].tag;
            T[T[p].lson].sum += T[p].tag*(mid-l+1LL);
            T[T[p].rson].sum += T[p].tag*(r-mid);
        }
        T[p].tag = 0;
    }
}
ll ask(int p,ll L,ll R,ll l,ll r) {
    if(L<=l&&r<=R) return T[p].sum;
    push_down(p,l,r);
    ll mid = (l+r)>>1LL;
    if(mid>=R) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        return ask(T[p].lson,L,R,l,mid);
    }
    else if(mid < L) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        return ask(T[p].rson,L,R,mid+1LL,r);
    }
    else {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        return ask(T[p].lson,L,mid,l,mid)+ask(T[p].rson,mid+1LL,R,mid+1LL,r);
    }
}
void push_up(int p) {
    T[p].sum = (T[p].lson!=-1)*T[T[p].lson].sum + (T[p].rson!=-1)*T[T[p].rson].sum;
}

void add(int p,ll L,ll R,ll l,ll r,ll x) {
    if(L<=l&&r<=R) {
        T[p].tag += x;
        T[p].sum += (r-l+1LL)*x;
        return;
    }
    push_down(p,l,r);
    ll mid = (l+r)>>1LL;
    if(mid>=R) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        add(T[p].lson,L,R,l,mid,x);
    }
    else if(mid < L) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        add(T[p].rson,L,R,mid+1LL,r,x);
    }
    else {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        add(T[p].lson,L,mid,l,mid,x),add(T[p].rson,mid+1LL,R,mid+1LL,r,x);
    }
    push_up(p);
}

int main() {
    int q;
    scanf("%d",&q);
    cnt = 0;
    int rt = ++cnt;int K=0;
    ll res = 0;
    T[rt].sum = 0;T[rt].lson=T[rt].rson = -1;T[rt].tag = 0;
    while(q--) {int opt;ll L,R,x;
        scanf("%d",&opt);
        if(opt) {
            scanf("%lld%lld",&L,&R);
            printf("%lld
",ask(rt,L,R,0,1000000000LL));
        }
        else {
            scanf("%lld%lld%lld",&L,&R,&x);
            add(rt,L,R,0,1000000000LL,x);
        }
    }
    return 0;
}

H. 万恶的柯怡

#include <bits/stdc++.h>
typedef long long ll;
const int N = 4000010;
using namespace std;
struct node{
    ll sum,tag;int lson,rson;
}T[N];
int cnt;
void newnode(int &x,ll sum) {
    x = ++cnt;
    T[x].sum = sum;
    T[x].lson = T[x].rson = -1;
    T[x].tag = 0;
}
void push_down(int p,ll l,ll r) {
    ll mid = (l+r) >> 1LL;
    if(T[p].tag) {
        if(T[p].lson==-1&&T[p].rson==-1){
            newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
            newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
            T[T[p].lson].tag += T[p].tag;
            T[T[p].rson].tag += T[p].tag;
        }
        else {
            T[T[p].lson].tag += T[p].tag;
            T[T[p].rson].tag += T[p].tag;
            T[T[p].lson].sum += T[p].tag*(mid-l+1LL);
            T[T[p].rson].sum += T[p].tag*(r-mid);
        }
        T[p].tag = 0;
    }
}
ll ask(int p,ll L,ll R,ll l,ll r) {
    if(L<=l&&r<=R) return T[p].sum;
    push_down(p,l,r);
    ll mid = (l+r)>>1LL;
    if(mid>=R) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        return ask(T[p].lson,L,R,l,mid);
    }
    else if(mid < L) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        return ask(T[p].rson,L,R,mid+1LL,r);
    }
    else {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        return ask(T[p].lson,L,mid,l,mid)+ask(T[p].rson,mid+1LL,R,mid+1LL,r);
    }
}
void push_up(int p) {
    T[p].sum = (T[p].lson!=-1)*T[T[p].lson].sum + (T[p].rson!=-1)*T[T[p].rson].sum;
}

void add(int p,ll L,ll R,ll l,ll r,ll x) {
    if(L<=l&&r<=R) {
        T[p].tag += x;
        T[p].sum += (r-l+1LL)*x;
        return;
    }
    push_down(p,l,r);
    ll mid = (l+r)>>1LL;
    if(mid>=R) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        add(T[p].lson,L,R,l,mid,x);
    }
    else if(mid < L) {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        add(T[p].rson,L,R,mid+1LL,r,x);
    }
    else {
        if(T[p].lson==-1) newnode(T[p].lson,T[p].sum/(r-l+1LL)*(mid-l+1LL));
        if(T[p].rson==-1) newnode(T[p].rson,T[p].sum/(r-l+1LL)*(r-mid));
        add(T[p].lson,L,mid,l,mid,x),add(T[p].rson,mid+1LL,R,mid+1LL,r,x);
    }
    push_up(p);
}

int main() {
    int TT;
    scanf("%d",&TT);
    while(TT--) {
        int q;
        scanf("%d",&q);
        cnt = 0;
        int rt = ++cnt;int K=0;
        ll res = 0;
        T[rt].sum = 0;T[rt].lson=T[rt].rson = -1;T[rt].tag = 0;
        while(q--) {ll l,r,keyiL,keyiR,x;
            scanf("%lld %lld %lld %lld %lld",&l,&r,&x,&keyiL,&keyiR);
            l=l^res;r=r^res;keyiL=keyiL^res;keyiR=keyiR^res;
            if(l>r)swap(l,r);if(keyiL>keyiR)swap(keyiL,keyiR);
            add(rt,l,r,0,1000000000,x);
            res = ask(rt,keyiL,keyiR,0,1000000000);
            printf("%lld
",res);
            res %= 19980105;
        }
    }
    return 0;
}