先輩がまとめた線分樹の単点の増減・交代区間の増減

21877 ワード

データ構造線分樹

HDU 1166 HDU 1754 HDU 1394
HDU 1698 POJ 3468

//     /  ，    

#include 
#include 
using namespace std;

// lson, rson            ，           
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN =   n;
const int INF = 0x3f3f3f3f;

int MIN[MAXN<<2], MAX[MAXN<<2], SUM[MAXN<<2];

void PushUp(int rt) { //     ，rt          
    SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
    MIN[rt] = min(MIN[rt<<1], MIN[rt<<1|1]);
    MAX[rt] = max(MAX[rt<<1], MAX[rt<<1|1]);
}

//         ：
// l, r                   [l, r]
// rt             

//           l, r, rt       (1, n, 1)
// (1, n, 1)       1 ，     [1, n]    ，    
void Build(int l, int r, int rt) {
    if(l == r) {
        //         0    
        SUM[rt] = MAX[rt] = MIN[rt] = 0;
        //          ，    O(n)，    n               O(nlogn)
        // scanf("%d", &SUM[rt]);
        // MIN[rt] = MAX[rt] = SUM[rt];
        return;
    }
    int m = (l + r) >> 1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

//     ，  p        v
void UpdateV(int p, int v, int l, int r, int rt) {
    if(l == r) { //         ，      
        SUM[rt] = v;
        MIN[rt] = v;
        MAX[rt] = v;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) UpdateV(p, v,lson); //      ，       
    else UpdateV(p, v, rson); //         
    PushUp(rt); //           
}

//     ，  p        d
void UpdateD(int p, int d, int l, int r, int rt) {
    if(l == r) {
        SUM[rt] = SUM[rt] + d;
        MIN[rt] = MIN[rt] + d;
        MAX[rt] = MAX[rt] + d;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) UpdateD(p, d, lson);
    else UpdateD(p, d, rson);
    PushUp(rt);
}

//   L~R   
int QuerySum(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return SUM[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret += QuerySum(L, R, lson); //         ，      
    if(R > m) ret += QuerySum(L, R, rson); //         ，      

    return ret;
}

//   L~R     
int QueryMin(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return MIN[rt];
    int m = (l + r) >> 1;
    int ret = INF;
    if(L <= m) ret = min(ret, QueryMin(L, R, lson));
    if(R > m) ret = min(ret, QueryMin(L, R, rson));

    return ret;
}

//   L~R     
int QueryMax(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return MAX[rt];
    int m = (l + r) >> 1;
    int ret = -INF;
    if(L <= m) ret = max(ret, QueryMax(L, R, lson));
    if(R > m) ret = max(ret, QueryMax(L, R, rson));

    return ret;
}

//     ，    

#include 
#include 
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN =   n;
const int INF = 0x3f3f3f3f;

int SUM[MAXN<<2], MIN[MAXN<<2], MAX[MAXN<<2];
int lazy[MAXN<<2];

void PushUp(int rt) { //     、          
    SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
    MIN[rt] = min(MIN[rt<<1], MIN[rt<<1|1]);
    MAX[rt] = max(MAX[rt<<1], MAX[rt<<1|1]);
}

void PushDown(int rt, int m) { //     
    if(lazy[rt]) {
        lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
        SUM[rt<<1] = (m - (m >> 1)) * lazy[rt];
        SUM[rt<<1|1] = ((m >> 1)) * lazy[rt];
        MIN[rt<<1] = MIN[rt<<1|1] = lazy[rt];
        MAX[rt<<1] = MAX[rt<<1|1] = lazy[rt];
        lazy[rt] = 0;
    }
}

//     l, r, rt    1, n, 1
void Build(int l, int r, int rt) {
    lazy[rt] = 0;
    if(l== r) {
        //       0    
        SUM[rt] = MIN[rt] = MAX[rt] = 0; 
        //          
        // scanf("%d", &SUM[rt]);  
        // MIN[rt] = MAX[rt] = SUM[rt];
        return;
    }
    int m = (l + r) >> 1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

//   L~R        v
void Update(int L, int R, int v, int l, int r, int rt) {
    if(L<=l && r<=R) {
        lazy[rt] = v;
        SUM[rt] = v * (r - l + 1);
        MIN[rt] = v;
        MAX[rt] = v;
        return;
    }
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    if(L <= m) Update(L, R, v, lson);
    if(R > m) Update(L, R, v, rson);
    PushUp(rt);
}

//     L~R   
int QuerySum(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return SUM[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret += QuerySum(L, R, lson);
    if(R > m) ret += QuerySum(L, R, rson);

    return ret;
}

//     L~R     
int QueryMin(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return MIN[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    int ret = INF;
    if(L <= m) ret = min(ret, QueryMin(L, R, lson));
    if(R > m) ret = min(ret, QueryMin(L, R, rson));

    return ret;
}

//     L~R     
int QueryMax(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return MAX[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    int ret = -INF;
    if(L <= m) ret = max(ret, QueryMax(L, R, lson));
    if(R > m) ret = max(ret, QueryMax(L, R, rson));

    return ret;
}

//     ，    

#include 
#include 
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN =   n;
const int INF = 0x3f3f3f3f;

int SUM[MAXN<<2], MIN[MAXN<<2], MAX[MAXN<<2];
int lazy[MAXN<<2];

void PushUp(int rt) {
    SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
    MIN[rt] = min(MIN[rt<<1], MIN[rt<<1|1]);
    MAX[rt] = max(MAX[rt<<1], MAX[rt<<1|1]);
}

void PushDown(int rt, int m) {
    if(lazy[rt]) {
        lazy[rt<<1] += lazy[rt];
        lazy[rt<<1|1] += lazy[rt];
        SUM[rt<<1] += lazy[rt] * (m - (m >> 1));
        SUM[rt<<1|1] += lazy[rt] * (m >> 1);
        MIN[rt<<1] += lazy[rt];
        MIN[rt<<1|1] += lazy[rt];
        MAX[rt<<1] += lazy[rt];
        MAX[rt<<1|1] += lazy[rt];
        lazy[rt] = 0;
    }
}

//     l, r, rt    1, n, 1
void Build(int l, int r, int rt) {
    lazy[rt] = 0;
    if(l == r) {
        //       0    
        SUM[rt] = MIN[rt] = MAX[rt] = 0;
        //          
        // scanf("%d", &SUM[rt]);
        // MIN[rt] = MAX[rt] = SUM[rt];
        return;
    }
    int m = (l + r) >> 1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

//     L~R      v
void Update(int L, int R, int v, int l, int r, int rt) {
    if(L<=l && r<=R) {
        lazy[rt] += v;
        SUM[rt] += v * (r - l + 1);
        MIN[rt] += v;
        MAX[rt] += v;
        return;
    }
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    if(L <= m) Update(L, R, v, lson);
    if(R > m) Update(L, R, v, rson);
    PushUp(rt);
}

//     L~R   
int QuerySum(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return SUM[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret += QuerySum(L, R, lson);
    if(R > m) ret += QuerySum(L, R, rson);

    return ret;
}

//     L~R     
int QueryMin(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return MIN[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    int ret = INF;
    if(L <= m) ret = min(ret, QueryMin(L, R, lson));
    if(R > m) ret = min(ret, QueryMin(L, R, rson));

    return ret;
}

//     L~R     
int QueryMax(int L, int R, int l, int r, int rt) {
    if(L<=l && r<=R) return MAX[rt];
    PushDown(rt, r-l+1);
    int m = (l + r) >> 1;
    int ret = -INF;
    if(L <= m) ret = max(ret, QueryMax(L, R, lson));
    if(R > m) ret = max(ret, QueryMax(L, R, rson));

    return ret;
}

山を積むprorityqueue.山の頂