This documentation is automatically generated by online-judge-tools/verification-helper
#include "datastructure/top_k_sum.hpp"Compare 順に並べたときの先頭 $k$ 個の和を保つ。top_k_sum<T, Compare = std::greater<T>>(k): 空の多重集合を作る。std::greater なら大きい方から $k$ 個の和、std::less なら小さい方から $k$ 個の和。insert(x): x を 1 個追加する。erase(x): x を 1 個削除する。x は含まれていなければならない。set_k(k): $k$ を k に設定する。k(): $k$ を返す。sum(): 先頭 $k$ 個の和を返す。要素が $k$ 個未満なら全要素の和を返す。size(): 要素の個数を返す。T は +=, -=, == を持つinsert, erase: 償却 $\mathcal{O}(\log N)$set_k: 償却 $\mathcal{O}(\lvert k - k’ \rvert \log N)$k, sum, size: $\mathcal{O}(1)$#pragma once
#include <cassert>
#include <functional>
#include <queue>
#include <vector>
template <class T, class Compare = std::greater<T>>
struct top_k_sum {
public:
explicit top_k_sum(int k) : _k(k), _sum(T()) {
assert(k >= 0);
}
void insert(const T& x) {
in.push(x);
_sum += x;
modify();
}
void erase(const T& x) {
assert(size() > 0);
if (!in.empty() && in.top() == x) {
_sum -= x;
in.pop();
} else if (!in.empty() && Compare()(x, in.top())) {
_sum -= x;
d_in.push(x);
} else {
d_out.push(x);
}
modify();
}
void set_k(int k) {
assert(k >= 0);
_k = k;
modify();
}
int k() const {
return _k;
}
T sum() const {
return _sum;
}
int size() const {
return int(in.size() + out.size() - d_in.size() - d_out.size());
}
private:
struct reverse_compare {
bool operator()(const T& a, const T& b) const {
return Compare()(b, a);
}
};
std::priority_queue<T, std::vector<T>, Compare> in, d_in;
std::priority_queue<T, std::vector<T>, reverse_compare> out, d_out;
int _k;
T _sum;
int in_size() const {
return int(in.size() - d_in.size());
}
void modify() {
while (in_size() < _k && !out.empty()) {
T p = out.top();
out.pop();
if (!d_out.empty() && p == d_out.top()) {
d_out.pop();
} else {
_sum += p;
in.push(p);
}
}
while (in_size() > _k) {
T p = in.top();
in.pop();
if (!d_in.empty() && p == d_in.top()) {
d_in.pop();
} else {
_sum -= p;
out.push(p);
}
}
while (!d_in.empty() && in.top() == d_in.top()) {
in.pop();
d_in.pop();
}
}
};#line 2 "datastructure/top_k_sum.hpp"
#include <cassert>
#include <functional>
#include <queue>
#include <vector>
template <class T, class Compare = std::greater<T>>
struct top_k_sum {
public:
explicit top_k_sum(int k) : _k(k), _sum(T()) {
assert(k >= 0);
}
void insert(const T& x) {
in.push(x);
_sum += x;
modify();
}
void erase(const T& x) {
assert(size() > 0);
if (!in.empty() && in.top() == x) {
_sum -= x;
in.pop();
} else if (!in.empty() && Compare()(x, in.top())) {
_sum -= x;
d_in.push(x);
} else {
d_out.push(x);
}
modify();
}
void set_k(int k) {
assert(k >= 0);
_k = k;
modify();
}
int k() const {
return _k;
}
T sum() const {
return _sum;
}
int size() const {
return int(in.size() + out.size() - d_in.size() - d_out.size());
}
private:
struct reverse_compare {
bool operator()(const T& a, const T& b) const {
return Compare()(b, a);
}
};
std::priority_queue<T, std::vector<T>, Compare> in, d_in;
std::priority_queue<T, std::vector<T>, reverse_compare> out, d_out;
int _k;
T _sum;
int in_size() const {
return int(in.size() - d_in.size());
}
void modify() {
while (in_size() < _k && !out.empty()) {
T p = out.top();
out.pop();
if (!d_out.empty() && p == d_out.top()) {
d_out.pop();
} else {
_sum += p;
in.push(p);
}
}
while (in_size() > _k) {
T p = in.top();
in.pop();
if (!d_in.empty() && p == d_in.top()) {
d_in.pop();
} else {
_sum -= p;
out.push(p);
}
}
while (!d_in.empty() && in.top() == d_in.top()) {
in.pop();
d_in.pop();
}
}
};