What is ordered_set?
A GNU extension data structure similar to std::set, but it supports the following two operations in $\mathcal{O}(\log N)$ time:
order_of_key(k): the number of elements strictly less than kfind_by_order(k): the $k$-th element in ascending order (zero-based)
Useful when elements are frequently inserted/erased and you often need to query the $k$-th smallest element.
1
2
3
4
5
6
7
| #include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set os;
|
However, deletion by value needs a small helper:
1
2
3
4
5
| void erase(ordered_set &os, int value) {
size_t index = os.order_of_key(value);
auto iter = os.find_by_order(index);
os.erase(iter);
}
|
ordered_set example
order_of_key returns a value. find_by_order returns an iterator.
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
| #include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
void erase(ordered_set &os, int value) {
size_t index = os.order_of_key(value);
auto iter = os.find_by_order(index);
os.erase(iter);
}
int main() {
ordered_set os;
os.insert(5);
os.insert(4);
os.insert(3);
os.insert(3);
os.insert(2);
os.insert(1);
for (int i : os) cout << i << ' '; // 1 2 3 4 5
cout << os.order_of_key(2) << endl; // 1
cout << *os.find_by_order(2) << endl; // 3
cout << os.size() << endl; // 5
erase(os, 2);
cout << os.size() << endl; // 4
for (int i : os) cout << i << ' '; // 1 3 4 5
cout << os.order_of_key(2) << endl; // 1
cout << *os.find_by_order(2) << endl; // 4
}
|
ordered_multi_set example
Allows duplicates.
Use less_equal<> instead of less<>.
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
| #include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_multi_set;
void erase(ordered_multi_set &oms, int value) {
size_t index = oms.order_of_key(value);
auto iter = oms.find_by_order(index);
oms.erase(iter);
}
int main() {
ordered_multi_set oms;
oms.insert(5);
oms.insert(4);
oms.insert(3);
oms.insert(3);
oms.insert(2);
oms.insert(1);
for (int i : oms) cout << i << ' '; // 1 2 3 3 4 5
cout << oms.order_of_key(2) << endl; // 1
cout << *oms.find_by_order(2) << endl; // 3
cout << oms.size() << endl; // 6
erase(oms, 2);
cout << oms.size() << endl; // 5
for (int i : oms) cout << i << ' '; // 1 3 3 4 5
cout << oms.order_of_key(2) << endl; // 1
cout << *oms.find_by_order(2) << endl; // 3
}
|
https://www.acmicpc.net/problem/1572
Although this is a segment tree/binary search problem, PBDS makes it straightforward.
Solution idea
A temperature reading arrives every second. Compute the sum of medians over the last $K$ seconds.
Insert each value into an ordered_multi_set each second.
Before time $K$, only insert values. From time $K$ onward, query the median each step. Remember that find_by_order() is zero-based.
We only care about the most recent $K$ values, so after time $K$ remove the value that fell out of the window.
Since duplicates can occur, use less_equal<>. The answer fits within $2^{63}-1$, so it exceeds int.
