「Note」权值线段树

Posted on Edited on In

权值线段树初步

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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = 1e9;

int q, tot = 1;

struct SegmentTree {
	int lc, rc;
	int cnt, del;
} s[MAXN * 30];

void pushup(int p) {
	s[p].cnt = s[s[p].lc].cnt + s[s[p].rc].cnt;
	return;
}

void pushdown(int p) {
	if (s[p].del == 1) {
		s[p].del = 0;
		s[s[p].lc].del = 1;
		s[s[p].rc].del = 1;
		s[s[p].lc].cnt = 0;
		s[s[p].rc].cnt = 0;
	} 
}

void update(int p, int l, int r, int id) {
	if (l == r) {
		s[p].del = 0;
		s[p].cnt++;
		return;
	}
	pushdown(p);
	int mid = (l + r) >> 1;
	if (id <= mid) {
		if (s[p].lc == 0) s[p].lc = ++tot;
		update(s[p].lc, l, mid, id);
	} else {
		if (s[p].rc == 0) s[p].rc = ++tot;
		update(s[p].rc, mid + 1, r, id);
	}
	pushup(p);
}

void clean(int p, int l, int r, int ql, int qr) {
	if (s[p].cnt == 0 || s[p].del == 1 || p == 0) return;
	if (l >= ql && qr >= r) {
		s[p].cnt = 0;
		s[p].del = 1;
		return;
	}
	pushdown(p);
	int mid = (l + r) >> 1;
	if (ql <= mid) {
		clean(s[p].lc, l, mid, ql, qr);
	}
	if (qr > mid) {
		clean(s[p].rc, mid + 1, r, ql, qr);
	}
	pushup(p);
}

int sum(int p, int l, int r, int ql, int qr) {
	if (s[p].cnt == 0 || s[p].del == 1 || p == 0) return 0;
	if (l >= ql && qr >= r) {
		return s[p].cnt;
	}
	pushdown(p);
	int val = 0;
	int mid = (l + r) >> 1;
	if (ql <= mid) {
		val += sum(s[p].lc, l, mid, ql, qr);
	}
	if (qr > mid) {
		val += sum(s[p].rc, mid + 1, r, ql, qr); 
	}
	return val;
}

int querykth(int p, int l, int r, int ql, int qr, int k) {
	if (s[p].cnt == 0 || s[p].del == 1 || p == 0) return -1;
	if (l == r) {
		if (s[p].cnt >= k) return l;
		else return -1;
	}
	pushdown(p);
	int mid = (l + r) >> 1, cnt = 0;
	if (qr > mid) {
		cnt = sum(s[p].rc, mid + 1, r, ql, qr);
		if (cnt >= k) return querykth(s[p].rc, mid + 1, r, ql, qr, k);
	} 
	if (ql <= mid) {
		return querykth(s[p].lc, l, mid, ql, qr, k - cnt);
	}
	return -1;
}

int main() {
	scanf ("%d", &q);
	while (q--) {
		int opt, x, l, r, k;
		scanf ("%d", &opt);
		if (opt == 1) {
			scanf ("%d", &x);
			update(1, 1, 1e9, x);
		}
		if (opt == 2) {
			scanf ("%d %d", &l, &r);
			clean(1, 1, 1e9, l, r);
		}
		if (opt == 3) {
			scanf ("%d %d %d", &l, &r, &k);
			printf ("%d\n", querykth(1, 1, 1e9, l, r, k));
		}
	}
	return 0;
}

The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」