COGS2554 - 可持久化线段树

2016/11/21

一道裸题,见识到了主席树。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <limits>
#include <cstdio>
#ifdef LCYTEST
#   define test(_x) { _x; }
#else
#   define test(_x) { ; }
#endif
using namespace std;
const int MAX_N = 10000 + 1000;
const int MAX_Q = 100000 + 1000;
const int PSIZ = 1500000;
int Q, N;

struct jnod {
    int max;
    int L, R;
    jnod* s[2];
} POOL[PSIZ]; int ppos;
jnod* Head[MAX_Q]; int vpos;
int Src[MAX_N];

jnod* mkJnod() {
    return &POOL[ppos++];
}

void mkTree(jnod* &cur, int L, int R) {
    if(!cur) cur = mkJnod();
    cur->L = L; cur->R = R;
    if(cur->L == cur->R) {
        cur->max = Src[L];
    } else {
        int Mid = (L + R) >> 1;
        mkTree(cur->s[0], L, Mid); mkTree(cur->s[1], Mid+1, R);
        cur->max = max(cur->s[0]->max, cur->s[1]->max);
    }
}

int change(jnod* lcur, jnod* &ncur, int p, int v) {
    test({ cout << ncur << endl; });
    if(!ncur) ncur = mkJnod();
    ncur->L = lcur->L; ncur->R = lcur->R;
    if(lcur->L == lcur->R) {
        ncur->max = v;
    } else {
        int Mid = (lcur->L + lcur->R) >> 1;
        if(p <= Mid) {
            change(lcur->s[0], ncur->s[0], p, v);
            ncur->s[1] = lcur->s[1];
        } else {
            change(lcur->s[1], ncur->s[1], p, v);
            ncur->s[0] = lcur->s[0];
        }

        ncur->max = max(ncur->s[0]->max, ncur->s[1]->max);
    }
}

int query(jnod* cur, int L, int R) { // [L, R]
    // if(!cur) return numeric_limits<int>::min();
    test({ cout << cur << " " << L << " " << R << " @ " << cur->L << " " << cur->R << endl; });
    if(cur->L >= L && cur->R <= R) return cur->max;
    int Mid = (cur->L + cur->R) >> 1;
    int ret = numeric_limits<int>::min();
    if(L <= Mid) ret = max(ret, query(cur->s[0], L, R));
    if(R >  Mid) ret = max(ret, query(cur->s[1], L, R));
    return ret;
}

int main() {
    freopen("longterm_segtree.in", "r", stdin);
    freopen("longterm_segtree.out", "w", stdout);

    cin >> N >> Q;
    for(int i=1;i<=N;i++) cin >> Src[i];
   
    vpos = 1;
    mkTree(Head[vpos++], 1, N);  

    int a, b, c, d;
    for(int i=1;i<=Q;i++) {
        cin >> a >> b >> c >> d;
        switch(a) {
            case 0: cout << query(Head[b], c, d) << endl; break;
            case 1: change(Head[b], Head[vpos++], c, d); break;
        }
    }
}