本节内容主要针对一些数据结构进行优化
包括线段树延迟标记，扫描线

线段树延迟标记

延迟标记表示该节点已经被修改了
但是子节点尚未被更新

线段树的延迟标记一般有一下几种

  • 将区间内的值全部都增加 addadd
  • 将区间内的值重新设置 setset

一般 sum,minv,maxvsum, minv, maxv 不作为延迟标记
这些值常常是用来维护的
要注意延迟标记对这些维护值的影响，比如
sum+=add∗(R−L)sum += add * (R-L)

POJ3468

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

const int maxn = 100000 + 10;
int A[maxn], n, m;

class segTree {
public:
    int l, r;
    llong sum, tag;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define tag(x) tree[x].tag
} tree[maxn * 4];

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    //debug(p);
    if(l == r) {
        sum(p) = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);

    sum(p) = sum(p << 1) + sum(p << 1 | 1);
}

void spread(int p) {
    if(tag(p)) {
        sum(p << 1) += tag(p) * (r(p<<1) - l(p<<1) + 1);
        sum(p << 1 | 1) += tag(p) * (r(p<<1 | 1) - l(p<<1 | 1) + 1);
        tag(p << 1) += tag(p);
        tag(p << 1 | 1) += tag(p);
        tag(p) = 0;
    }
}

void change(int p, int l, int r, int d) {
    if(l <= l(p) && r(p) <= r) {
        sum(p) += (llong)d * (r(p) - l(p) + 1);
        tag(p) += d;
        return;
    }
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    if(l <= mid) change(p<<1, l, r, d);
    if(r > mid) change(p<<1 | 1, l, r, d);

    sum(p) = sum(p<<1) + sum(p<<1 | 1);
}

llong ask(int p, int l, int r) {
    if(l <= l(p) && r(p) <= r) return sum(p);
    spread(p);

    int mid = (l(p) + r(p)) >> 1;
    llong val = 0;
    if(l <= mid) val += ask(p<<1, l, r);
    if(r > mid) val += ask(p<<1 | 1, l, r);
    return val;
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;
    _rep(i, 1, n) scanf("%d", &A[i]);

    build(1, 1, n);

    while (m--) {
        char op[2];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        if(op[0] == 'C') {
            int d;
            scanf("%d", &d);
            change(1, l, r, d);
        }
        else printf("%lld\n", ask(1, l, r));
    }
}

线段树多延迟标记

UVA11992
UVA11992

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;

int minn = inf, maxx = -inf, sum = 0;

void initqry() {
    minn = inf;
    maxx = -inf;
    sum = 0;
}

class SegTree {
public:
    int l, r;
    int sumv, maxv, minv;
    int addfl, setfl;

    void clear() {
        l = r = 0;
        sumv = maxv = minv = 0;
        addfl = 0;
        setfl = -1;
    }
} tree[maxn * 4];

void build(int p, int l, int r) {
    tree[p].clear();
    tree[p].l = l; tree[p].r = r;

    if (l == r) return;

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1 | 1, mid + 1, r);
}

void pushup(int p) {
    tree[p].sumv = tree[p<<1].sumv + tree[p<<1 | 1].sumv;
    tree[p].maxv = max(tree[p<<1].maxv, tree[p<<1 | 1].maxv);
    tree[p].minv = min(tree[p<<1].minv, tree[p<<1 | 1].minv);
}

void pushdown(int p) {
    if (tree[p].setfl >= 0) {
        int fl = tree[p].setfl;

        tree[p<<1].setfl = tree[p<<1 | 1].setfl = fl;
        tree[p<<1].addfl = tree[p<<1 | 1].addfl = 0;
        tree[p<<1].minv = tree[p<<1 | 1].minv = fl;
        tree[p<<1].maxv = tree[p<<1 | 1].maxv = fl;
        tree[p<<1].sumv = fl * (tree[p<<1].r - tree[p<<1].l + 1);
        tree[p<<1 | 1].sumv = fl * (tree[p<<1 | 1].r - tree[p<<1 | 1].l + 1);

        tree[p].setfl = -1;
    }

    if (tree[p].addfl > 0) {
        int fl = tree[p].addfl;

        tree[p<<1].addfl += fl;
        tree[p<<1 | 1].addfl += fl;

        tree[p<<1].maxv += fl;
        tree[p<<1 | 1].maxv += fl;

        tree[p<<1].minv += fl;
        tree[p<<1 | 1].minv += fl;

        tree[p<<1].sumv += fl * (tree[p<<1].r - tree[p<<1].l + 1);
        tree[p<<1 | 1].sumv += fl * (tree[p<<1 | 1].r - tree[p<<1 | 1].l + 1);

        tree[p].addfl = 0;
    }
}

void change1(int p, int l, int r, int v) {
    // set
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sumv = v * (tree[p].r - tree[p].l + 1);
        tree[p].maxv = tree[p].minv = v;

        tree[p].setfl = v; tree[p].addfl = 0;
        return;
    }

    pushdown(p);

    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) change1(p<<1, l, r, v);
    if (r > mid) change1(p<<1 | 1, l, r, v);

    pushup(p);
}

void change2(int p, int l, int r, int v) {
    // add
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sumv += v * (tree[p].r - tree[p].l + 1);
        tree[p].maxv += v;
        tree[p].minv += v;
        tree[p].addfl += v;
        return;
    }

    pushdown(p);

    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) change2(p<<1, l, r, v);
    if (r > mid) change2(p<<1 | 1, l, r, v);

    pushup(p);
}

void query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) {
        sum += tree[p].sumv;
        chmax(maxx, tree[p].maxv);
        chmin(minn, tree[p].minv);
        return;
    }

    pushdown(p);

    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) query(p<<1 , l, r);
    if (r > mid) query(p<<1 | 1, l, r);

    pushup(p);
}

int r, c, m;

int main() {
    //freopen("input.txt", "r", stdin);
    while (scanf("%d%d%d", &r, &c, &m) == 3) {
        int op, x1, x2, y1, y2, v;

        build(1, 1, r*c);

        while (m--) {
            scanf("%d", &op);

            if (op == 1) {
                scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);
                _rep(i, x1, x2) {
                    int le = (i-1) * c + y1, ri = (i - 1) * c + y2;
                    change2(1, le, ri, v);
                }
            }
            if (op == 2) {
                scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);
                _rep(i, x1, x2) {
                    int le = (i-1) * c + y1, ri = (i-1) * c + y2;
                    change1(1, le, ri, v);
                }
            }
            if (op == 3) {
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                initqry();
                _rep(i, x1, x2) {
                    int le = (i-1) * c + y1, ri = (i-1) * c + y2;
                    query(1, le, ri);
                }
                printf("%d %d %d\n", sum, minn, maxx);
            }
        }
    }
}

扫描线

POJ1151
POJ1151-01
POJ1151-02

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
89
90
91
92
93
94
95
96

const int maxn = 100 + 5;
int N, m;
int kase = 0;

class Node {
public:
    double x, y1, y2;
    int k;
    bool operator< (const Node& rhs) const {
        return x < rhs.x;
    }
};

Node A[maxn << 1];
map<double, int> ny;
double raw[maxn << 1];

void init() {
    Set(raw, 0);
    ny.clear();
}

void dicrete() {
    sort(raw + 1, raw + 1 + N);
    m = unique(raw + 1, raw + 1 + N) - (raw + 1);
    _rep(i, 1, m) ny[raw[i]] = i;
}

class Tree {
public:
    int l, r, cnt;
    double len;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define cnt(x) tree[x].cnt
#define len(x) tree[x].len
} tree[maxn << 3];

void build(int p, int l, int r) {
    l(p) = l; r(p) = r; len(p) = 0; cnt(p) = 0;
    if(l == r) return;

    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}

void change(int p, int l, int r, int d) {
    if(l <= l(p) && r(p) <= r) len(p) = ((cnt(p) += d) ? raw[r(p)+1] - raw[l(p)] : 0);
    if(l(p) == r(p)) return;

    int mid = (l(p) + r(p)) >> 1;
    if(l <= mid) change(p << 1, l, r, d);
    if(r > mid) change(p << 1 | 1, l, r, d);

    len(p) = (cnt(p) ? raw[r(p)+1] - raw[l(p)] : len(p<<1) + len(p<<1 | 1));
}

double atlantis() {
    sort(A + 1, A + 1 + N);
    build(1, 1, m - 1);
    // use subscribe to build seg tree

    double ans = 0;
    // scan line
    _for(i, 1, N) {
        int y1 = ny[A[i].y1], y2 = ny[A[i].y2] - 1;
        change(1, y1, y2, A[i].k);
        ans += len(1) * (A[i + 1].x - A[i].x);
    }
    printf("Test case #%d\nTotal explored area: %.2f\n\n", ++kase, ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (cin >> N && N) {
        init();

        _rep(i, 1, N) {
            int k = i << 1;
            double y1, y2;
            scanf("%lf %lf %lf %lf", &A[k-1].x, &y1, &A[k].x, &y2);
            raw[k-1] = A[k-1].y1 = A[k].y1 = y1;
            raw[k] = A[k-1].y2 = A[k].y2 = y2;
            A[k-1].k = 1;
            A[k].k = -1;
        }
        N <<= 1;

        // discrete()
        // oldY --ny()--> newY, raw[1-m]--> oldY
        dicrete();
        atlantis();
    }
}

扫描线周长问题

扫描线处理周长问题更为复杂
POJ1177

POJ1177-01
POJ1177-02

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

const int maxn = 5000 + 6;
const int maxv = 20000 + 7;
const int inf = 0x3f3f3f3f;
int n, tot;
int Max = -inf, Min = inf;

void init() {
    tot = 0;
    Max = -inf;
    Min = inf;
}

class L {
public:
    int x1, x2;
    int y;
    int st;
    bool operator< (const L& rhs) const {
        return y < rhs.y;
    }
};
L a[maxn << 1];

class segTree{
public:
    int l, r;
    bool lc, rc;
    int len;
    int cover;
    int cnt;
    // cnt: cover by discrete segment
} t[maxv << 2];

void build(int p, int l, int r) {
    t[p].l = l;
    t[p].r = r;
    t[p].lc = t[p].rc = 0;
    t[p].len = t[p].cnt = t[p].cover = 0;

    if(l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}

void check(int p) {
    if(t[p].cover) {
        t[p].len = t[p].r + 1 - t[p].l;
        t[p].lc = t[p].rc = 1;
        t[p].cnt = 1;
    }
    else if(t[p].l == t[p].r) {
        t[p].len = 0;
        t[p].lc = t[p].rc = 0;
        t[p].cnt = 0;
    }
    else {
        t[p].len = t[p<<1].len + t[p<<1 | 1].len;
        t[p].cnt = t[p<<1].cnt + t[p<<1 | 1].cnt;
        t[p].lc = t[p<<1].lc;
        t[p].rc = t[p<<1 | 1].rc;

        if(t[p<<1].rc && t[p<<1 | 1].lc) t[p].cnt--;
    }
}

void change(int p, int l, int r, int d) {
    if(l <= t[p].l && t[p].r <= r) {
        t[p].cover += d;
        check(p);
        return;
    }

    int mid = (t[p].l + t[p].r) >> 1;
    if(r <= mid) change(p << 1, l, r, d);
    else if(l > mid) change(p << 1 | 1, l, r, d);
    else {
        change(p << 1, l, mid, d);
        change(p << 1 | 1, mid + 1, r, d);
    }
    check(p);
}

void picture() {
    sort(a, a + tot);
    build(1, Min, Max - 1);

    int ans = 0, preOverlap = 0;
    _for(i, 0, tot) {
        change(1, a[i].x1, a[i].x2 - 1, a[i].st);
        ans += abs(preOverlap - t[1].len);
        ans += 2 * t[1].cnt * (a[i + 1].y - a[i].y);

        preOverlap = t[1].len;
    }
    cout << ans << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    init();
    int x1, y1, x2, y2;
    _for(i, 0, n) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        Max = max(Max, max(x1, x2));
        Min = min(Min, min(x1, x2));

        L& a1 = a[tot];
        L& a2 = a[tot + 1];

        a1.x1 = a2.x1 = x1;
        a1.x2 = a2.x2 = x2;

        a1.y = y1;
        a2.y = y2;

        a1.st = 1;
        a2.st = -1;

        tot += 2;
    }

    picture();
}

扫描线与坐标离散化

POJ2482
POJ2482-01
POJ2482-02

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

const int maxn = 10000 + 6;
unsigned int n, W, H;
int m;
// discrete n -> m

class R {
public:
    llong x;
    llong y1, y2;
    int c;
    bool operator< (const R& rhs) const {
        return x < rhs.x || (x == rhs.x && c < rhs.c);
    }
};

R a[maxn << 1];
llong raw[maxn << 1];
map<llong, int> ny;

void init() {
    //
    Set(raw, 0);
    ny.clear();
}

void discrete() {
    sort(raw + 1, raw + 1 + n);
    m = unique(raw + 1, raw + 1 + n) - raw - 1;

    _rep(i, 1, m) {
        ny[raw[i]] = i;
    }
}

class segTree {
public:
    int l, r, dat, tag;
#define l(p) t[p].l
#define r(p) t[p].r
#define dat(p) t[p].dat
#define tag(p) t[p].tag
} t[maxn << 3];

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    dat(p) = tag(p) = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1 | 1, mid + 1, r);
}

void spread(int p) {
    tag(p<<1) += tag(p);
    dat(p<<1) += tag(p);;

    tag(p<<1 | 1) += tag(p);
    dat(p<<1 | 1) += tag(p);

    tag(p) = 0;
}

void change(int p, int l, int r, int c) {
    if(l <= l(p) && r(p) <= r) {
        dat(p) += c;
        tag(p) += c;
        return;
    }

    if(tag(p)) spread(p);

    int mid = (l(p) + r(p)) >> 1;
    if(l <= mid) change(p<<1, l, r, c);
    if(r > mid) change(p<<1 | 1, l, r, c);

    dat(p) = max(dat(p<<1), dat(p<<1 | 1));
}

void starsWindow() {
    sort(a + 1, a + 1 + n);
    build(1, 1, m);

    int ans = 0;
    _rep(i, 1, n) {
        int y1 = ny[a[i].y1], y2 = ny[a[i].y2];
        change(1, y1, y2, a[i].c);
        ans = max(ans, dat(1));
    }
    cout << ans << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (cin >> n >> W >> H) {
        init();

        _rep(i, 1, n) {
            int k = (i<<1);
            cin >> a[k-1].x >> a[k-1].y1 >> a[k-1].c;
            a[k].x = a[k-1].x + W;
            raw[k-1] = a[k].y1 = a[k-1].y1;
            raw[k] = a[k].y2 = a[k-1].y2 = a[k-1].y1 + H - 1;
            a[k].c = -a[k-1].c;
        }
        // input finished
        n <<= 1;
        discrete();

        starsWindow();
    }
}

BST平衡二叉树

BST-01
BST-02
BST-03

treap树

GYM228544B
GYM228544B

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182

const int maxn = 100000 + 10;
const int inf = 0x3f3f3f3f;

class Treap {
public:
    int l, r;
    int val, rk;
    int cnt, sz;
};

Treap a[maxn];
int tot, root, n;

void init() {
    tot = 0;
}

int New(int val) {
    a[++tot].val = val;
    a[tot].rk = rand();
    a[tot].cnt = a[tot].sz = 1;
    return tot;
}

void Update(int p) {
    a[p].sz = a[a[p].l].sz + a[a[p].r].sz + a[p].cnt;
}

void build() {
    New(-inf), New(inf);
    root = 1, a[1].r = 2;
    Update(root);
}

int rankByVal(int p, int val) {
    if(p == 0) return 0;
    if(val == a[p].val) return a[a[p].l].sz + 1;
    if(val < a[p].val) return rankByVal(a[p].l, val);
    return a[a[p].l].sz + a[p].cnt + rankByVal(a[p].r, val);
}

int valByRank(int p, int rank) {
    if(p == 0) return inf;
    if(a[a[p].l].sz >= rank) return valByRank(a[p].l, rank);
    if(a[a[p].l].sz + a[p].cnt >= rank) return a[p].val;
    return valByRank(a[p].r, rank - a[a[p].l].sz - a[p].cnt);
}

void zig(int& p) {
    int q = a[p].l;
    a[p].l = a[q].r, a[q].r = p, p = q;
    Update(a[p].r), Update(p);
}

void zag(int& p) {
    int q = a[p].r;
    a[p].r = a[q].l, a[q].l = p, p = q;
    Update(a[p].l), Update(p);
}

void insert(int& p, int val) {
    if(p == 0) {
        p = New(val);
        return;
    }
    if(val == a[p].val) {
        a[p].cnt++;
        Update(p);
        return;;
    }

    if(val < a[p].val) {
        insert(a[p].l, val);
        if(a[p].rk < a[a[p].l].rk) zig(p);
    }
    else {
        insert(a[p].r, val);
        if(a[p].rk < a[a[p].r].rk) zag(p);
    }
    Update(p);
}

void remove(int& p, int val) {
    if(p == 0) return;
    if(val == a[p].val) {
        if(a[p].cnt > 1) {
            a[p].cnt--;
            Update(p);
            return;
        }

        if(a[p].l || a[p].r) {
            if(a[p].r == 0 || a[a[p].l].rk > a[a[p].r].rk) {
                zig(p);
                remove(a[p].r, val);
            }
            else {
                zag(p);
                remove(a[p].l, val);
            }

            Update(p);
        }
        else p = 0;
        return;
    }
    val < a[p].val ? remove(a[p].l, val) : remove(a[p].r, val);
    Update(p);
}

int getPre(int val) {
    int ans = 1;
    int p = root;

    while (p) {
        if(val == a[p].val) {
            if(a[p].l > 0) {
                p = a[p].l;
                while (a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }
        if(a[p].val < val && a[p].val > a[ans].val) ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[ans].val;
}

int getNext(int val) {
    int ans = 2;
    int p = root;

    while (p) {
        if(val == a[p].val) {
            if(a[p].r > 0) {
                p = a[p].r;
                while (a[p].l > 0) p = a[p].l;
                ans = p;
            }
            break;
        }

        if(a[p].val > val && a[p].val < a[ans].val) ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }

    return a[ans].val;
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    cin >> n;
    build();
    while (n--) {
        int op, x;
        scanf("%d%d", &op, &x);

        switch (op){
            case 1:
                insert(root, x);
                break;
            case 2:
                remove(root, x);
                break;
            case 3:
                printf("%d\n", rankByVal(root, x) - 1);
                break;
            case 4:
                printf("%d\n", valByRank(root, x + 1));
                break;
            case 5:
                printf("%d\n", getPre(x));
                break;
            case 6:
                printf("%d\n", getNext(x));
                break;
        }
    }
}

Treap树(内存回收)

HDU3726
HDU3726

Treap树删除的数组版本

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
void remove(int& p, int val) {
    if(p == 0) return;
    if(val == a[p].val) {
        if(a[p].cnt > 1) {
            a[p].cnt--;
            Update(p);
            return;
        }

        if(a[p].l && a[p].r) {
            if(a[a[p].l].rk > a[a[p].r].rk) {
                zig(p);
                remove(a[p].r, val);
            }
            else {
                zag(p);
                remove(a[p].l, val);
            }
        }
        else {
            if(a[p].l == 0 && a[p].r == 0) {
                p = 0;
                return;
            }
            else if(a[p].r == 0) p = a[p].l;
            else p = a[p].r;
        }
    }
    else {
        val < a[p].val ? remove(a[p].l, val) : remove(a[p].r, val);
    }
    if(p != 0) Update(p);
}

Treap树(回收内存)

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296

const int maxn = 20000 + 5;
const int maxm = 60000 + 5;
const int inf = 0x3f3f3f3f;
int n, m;
int weight[maxm], rmved[maxm];

// === treap tree ===

class Treap {
public:
    Treap* l;
    Treap* r;

    int val, dat;
    int sz;

    Treap(int val) : val(val) {
        l = r = NULL;
        dat = rand();
        sz = 1;
    }

    void update() {
        sz = 1;
        if(l != NULL) sz += l->sz;
        if(r != NULL) sz += r ->sz;
    }
};

typedef Treap* T;
T a[maxn];

void zig(T& p) {
    T q = p->l;
    p->l = q->r; q->r = p; p = q;

    p->r->update();
    p->update();
}

void zag(T& p) {
    T q = p->r;
    p->r = q->l; q->l = p; p = q;

    p->l->update();
    p->update();
}

void insert(T& p, int val) {
    if(p == NULL) {
        p = new Treap(val);
        return;
    }

    if(val < p->val) {
        insert(p->l, val);
        if(p->dat < p->l->dat) zig(p);
    }
    else {
        insert(p->r, val);
        if(p->dat < p->r->dat) zag(p);
    }
    p->update();
}


void remove(T& p, int val) {
    if(val == p->val) {
        T u = p;
        if(p->l && p->r) {
            if(p->l->dat > p->r->dat) {
                zig(p);
                remove(p->r, val);
            }
            else {
                zag(p);
                remove(p->l, val);
            }
        }
        else {
            if(p->l == NULL) p = p->r;
            else p = p->l;
            delete u;
        }
    }
    else {
        val < p->val ? remove(p->l, val) : remove(p->r, val);
    }
    if(p != NULL) p->update();
}


// pre is the max of min{}
int getPre(const T& root, int val) {
    int ans = -inf;
    T p = root;

    while (p) {
        if(val == p->val) {
            if(p->l != NULL) {
                p = p->l;
                while (p->r != NULL) p = p->r;
                ans = p->val;
            }
            break;
        }
        if(p->val < val && p->val > ans) ans = p->val;
        p = val < p->val ? p->l : p->r;
    }
    return ans;
}

// next is the min of max{}

int getNxt(const T& root, int val) {
    int ans = inf;
    T p = root;

    while (p) {
        if(val == p->val) {
            if(p->r != NULL) {
                p = p->r;
                while (p->l != NULL) p = p->l;
                ans = p->val;
            }
            break;
        }
        if(p->val > val && p->val < ans) ans = p->val;
        p = val < p->val ? p->l : p->r;
    }
    return ans;
}

int rankByVal(T p, int val) {
    if(p == NULL) return 0;
    if(val == p->val) return p->l->sz + 1;
    if(val < p->val) return rankByVal(p->l, val);
    return p->l->sz + 1 + rankByVal(p->r, val);
}

int valByRank(T p, int rank) {
    if(p == NULL || rank <= 0 || rank > p->sz) return 0;
    int s = p->r == NULL ? 0 : p->r->sz;

    if(rank == s + 1) return p->val;
    else if(rank <= s) return valByRank(p->r, rank);
    else return valByRank(p->l, rank - 1 - s);
}

// === treap tree finished ===


// === algorithm about forest
void mergeto(T& src, T& dest) {
    if(src->l != NULL) mergeto(src->l, dest);
    if(src->r != NULL) mergeto(src->r, dest);
    insert(dest, src->val);

    delete src;
    src = NULL;
}

void rmvTree(T& p) {
    if(p->l != NULL) rmvTree(p->l);
    if(p->r != NULL) rmvTree(p->r);
    delete p;
    p = NULL;
}

// === forest algorithm finished


class Edge {
public:
    int from, to;
};
Edge edges[maxm];


// === Union Find ===
int pa[maxn];
int findset(int x) {
    return pa[x] != x ? pa[x] = findset(pa[x]) : x;
}

void initpa(int n) {
    _rep(i, 1, n) pa[i] = i;
}

// === Union Find finished ===


// == main algorithm ==
void addEdge(int x) {
    int u = findset(edges[x].from), v = findset(edges[x].to);

    if(u != v) {
        if(a[u]->sz < a[v]->sz) {
            pa[u] = v;
            mergeto(a[u], a[v]);
        }
        else {
            pa[v] = u;
            mergeto(a[v], a[u]);
        }
    }
}

void changeWeight(int x, int v) {
    int u = findset(x);
    remove(a[u], weight[x]);
    insert(a[u], v);
    weight[x] = v;
}


llong ans = 0;
int qcnt = 0;

void query(int x, int k) {
    qcnt++;
    ans += valByRank(a[findset(x)], k);
}

// == main algorithm finished ==

// === get input ===
class CMD {
public:
    char type;
    int x, p;
};

vector<CMD> cmds;

void init() {
    Set(weight, 0);
    Set(rmved, 0);
    cmds.clear();

    ans = qcnt = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d%d", &n, &m) == 2 && n) {
        init();
        _rep(i, 1, n) scanf("%d", &weight[i]);
        _rep(i, 1, m) scanf("%d%d", &edges[i].from, &edges[i].to);

        // then read cmds
        for(;;) {
            char type;
            int x = 0, p = 0, v = 0;
            cin >> type;

            if(type == 'E') break;
            scanf("%d", &x);
            if(type == 'D') rmved[x] = 1;
            if(type == 'Q') scanf("%d", &p);
            if(type == 'C') {
                scanf("%d", &v);
                p = weight[x];
                weight[x] = v;
            }

            cmds.push_back((CMD) { type, x, p });
        }

        // read finished

        //initpa(n);

        // then build the last Graph

        _rep(i, 1, n) {
            pa[i] = i;
            if(a[i] != NULL) rmvTree(a[i]);
            a[i] = new Treap(weight[i]);
        }

        _rep(i, 1, m) if(!rmved[i]) addEdge(i);

        _forDown(i, cmds.size() - 1, 0) {
            if(cmds[i].type == 'D') addEdge(cmds[i].x);
            if(cmds[i].type == 'Q') query(cmds[i].x, cmds[i].p);
            if(cmds[i].type == 'C') changeWeight(cmds[i].x, cmds[i].p);
        }

        if(qcnt) printf("Case %d: %.6lf\n", ++kase, ans / (double)qcnt);
        else printf("Case %d: 0\n", ++kase);

    }
}