Partially Retroactive Priority Queue

概要

普通のPriority Queueが現在の列に対するPush、Popしか行えないのに対して、Retroactive Priority Queueは好きな時刻に操作を追加したり取り消したりできる。
また、Partially Retroactiveは現在の状態のみ、Fully Retroactiveは任意の時刻の状態を取得できる。

操作

実装

#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cassert>
constexpr int bit_ceil_log(unsigned int n) {
int x = 0;
while ((1 << x) < (unsigned int)(n)) x++;
return x;
}
template<typename T, typename cmp, T (*op)(T, T), T (*e)()>
struct partially_retroactive_priority_queue {
private:
static constexpr T null_val = std::numeric_limits<T>::max();
static constexpr T _min(T a, T b) { return (b == null_val || (a != null_val && cmp()(a, b))) ? a : b; }
static constexpr T _max(T a, T b) { return (a == null_val || (b != null_val && cmp()(a, b))) ? b : a; }
enum optype { ERASED, CURRENT, POP, NONE };
struct node {
int Ce, Cc, Cp;
int Dmin, mode;
T Me, Mc;
T x, sum;
node() : Ce(0), Cc(0), Cp(0), Dmin(0), mode(NONE), Me(null_val), Mc(null_val), sum(e()) {}
};
void to_current(int _v) {
node &v = d[_v];
v.mode = CURRENT;
v.Ce = v.Cp = v.Dmin = 0;
v.Cc = 1;
v.Me = null_val;
v.Mc = v.x;
v.sum = v.x;
while (_v > 1) {
_v /= 2;
update(_v);
}
}
void to_erased(int _v) {
node &v = d[_v];
v.mode = ERASED;
v.Ce = v.Dmin = 1;
v.Cc = v.Cp = 0;
v.Me = v.x;
v.Mc = null_val;
v.sum = e();
while (_v > 1) {
_v /= 2;
update(_v);
}
}
void to_pop(int _v) {
node &v = d[_v];
v.mode = POP;
v.Ce = v.Cc = 0;
v.Cp = 1;
v.Dmin = -1;
v.Me = v.Mc = null_val;
v.sum = e();
while (_v > 1) {
_v /= 2;
update(_v);
}
}
void to_none(int _v) {
node &v = d[_v];
v.mode = NONE;
v.Ce = v.Cc = v.Cp = v.Dmin = 0;
v.Me = v.Mc = null_val;
v.sum = e();
while (_v > 1) {
_v /= 2;
update(_v);
}
}
int log, sz;
std::vector<node> d;
void update(int _v) {
node &v = d[_v];
node &l = d[_v * 2];
node &r = d[_v * 2 + 1];
v.Ce = l.Ce + r.Ce;
v.Cc = l.Cc + r.Cc;
v.Cp = l.Cp + r.Cp;
v.Me = _max(l.Me, r.Me);
v.Mc = _min(l.Mc, r.Mc);
v.Dmin = std::min(l.Dmin, l.Ce - l.Cp + r.Dmin);
v.sum = op(l.sum, r.sum);
}
template<bool lmost>
int pos_dmin() const {
int v = 1;
while (v < sz) {
int cnt = d[v * 2].Ce - d[v * 2].Cp;
int RDmin = cnt + d[v * 2 + 1].Dmin;
if (d[v * 2].Dmin < RDmin + lmost) {
v = v * 2;
} else {
v = v * 2 + 1;
}
}
return v - sz;
}
int pos_Mc(int r) const {
int l = sz;
r += sz;
T Mc = null_val;
while (l < r) {
if (l & 1) Mc = _min(Mc, d[l++].Mc);
if (r & 1) Mc = _min(Mc, d[--r].Mc);
l >>= 1;
r >>= 1;
}
int v = 1;
while (v < sz) {
bool is_l = (_min(d[v * 2].Mc, Mc) == d[v * 2].Mc);
v = v * 2 + (!is_l);
}
return v - sz;
}
int pos_Me(int l) const {
l += sz;
int r = 2 * sz;
T Me = null_val;
while (l < r) {
if (l & 1) Me = _max(Me, d[l++].Me);
if (r & 1) Me = _max(Me, d[--r].Me);
l >>= 1;
r >>= 1;
}
int v = 1;
while (v < sz) {
bool is_r = (_max(d[v * 2 + 1].Me, Me) == d[v * 2 + 1].Me);
v = v * 2 + is_r;
}
return v - sz;
}
public:
partially_retroactive_priority_queue(int L) : log(bit_ceil_log(std::max(2, L))), sz(1 << log), d(2 * sz) {}
void set_op_push(int k, T x) {
assert(0 <= k && k < sz);
set_op_null(k);
d[sz + k].x = x;
to_erased(sz + k);
int l = (d[1].Dmin == 0 ? pos_dmin<false>() : 0);
int p = pos_Me(l);
to_current(sz + p);
}
// 空の状態でpopするような操作列に一度なると壊れる
// あらかじめinfをQ個pushしておけばいい
void set_op_pop(int k) {
assert(0 <= k && k < sz);
if (d[sz + k].mode == POP) return;
set_op_null(k);
to_pop(sz + k);
int r = pos_dmin<true>();
int p = pos_Mc(r);
to_erased(sz + p);
}
void set_op_null(int k) {
assert(0 <= k && k < sz);
int mode = d[sz + k].mode;
if (mode == NONE) return;
to_none(k + sz);
if (mode == ERASED) {
int p = pos_dmin<true>();
p = pos_Mc(p);
to_erased(sz + p);
}
if (mode == POP) {
int p = (d[1].Dmin == 0 ? pos_dmin<false>() : 0);
p = pos_Me(p);
to_current(sz + p);
}
}
int size() const {
return d[1].Cc;
}
bool empty() const {
return size() == 0;
}
T top() const {
assert(!empty());
return d[1].Mc;
}
// 残っている要素の追加した時刻の順のprod
T all_prod() const {
return d[1].sum;
}
};

使用例1

提出(ネタバレ注意)
#include <iostream>
#include <set>
using S = uint64_t;
static constexpr S op(S a, S b) {
return a + b;
}
static constexpr S e() {
return 0;
}
using ppq = partially_retroactive_priority_queue<S, std::greater<S>, op, e>;
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int N, Q;
std::cin >> N >> Q;
std::vector<int> D(N), P(N), Dcnt(N, 0);
std::vector<std::tuple<int, int, int>> QU(Q);
for (int i = 0; i < N; i++) {
std::cin >> D[i];
D[i]--;
Dcnt[D[i]]++;
}
for (int i = 0; i < N; i++) {
std::cin >> P[i];
}
for (int i = 0; i < Q; i++) {
int c, x, y;
std::cin >> c >> x >> y;
QU[i] = {c, x, y};
Dcnt[x - 1]++;
}
ppq q(3 * N + Q);
for (int i = 0; i < N; i++) q.set_op_push(i, 0);
std::vector<std::set<int>> empty_pos(N);
std::vector<int> used_pos(N);
int p = N;
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < Dcnt[i]; j++) {
empty_pos[i].insert(p + j);
}
p += Dcnt[i];
q.set_op_pop(p++);
}
S allsum = 0;
for (int i = 0; i < N; i++) {
allsum += P[i];
int d = D[i];
auto itr = empty_pos[d].begin();
used_pos[i] = *itr;
q.set_op_push(*itr, P[i]);
empty_pos[d].erase(itr);
}
for (int i = 0; i < Q; i++) {
auto [c, x, y] = QU[i];
c--, x--;
int d = D[c];
int p = used_pos[c];
empty_pos[d].insert(p);
q.set_op_null(p);
allsum -= P[c];
allsum += y;
D[c] = x;
P[c] = y;
auto itr = empty_pos[x].begin();
used_pos[c] = *itr;
q.set_op_push(*itr, y);
empty_pos[x].erase(itr);
std::cout << (allsum - q.all_prod()) << '\n';
}
}

使用例2

提出(ネタバレ注意)
#include <iostream>
using S = long long;
static constexpr S op(S a, S b) {
return a + b;
}
static constexpr S e() {
return 0;
}
using ppq = partially_retroactive_priority_queue<S, std::greater<S>, op, e>;
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int N, M;
std::cin >> N;
M = N / 2;
std::vector<long long> A(N);
long long sum = 0;
for (int i = 0; i < N; i++) {
std::cin >> A[i];
sum += A[i];
}
ppq pq(6 * M);
for (int i = 0; i < M; i++) {
int x = A[N - 2 * i - 1], y = A[N - 2 * i - 2];
pq.set_op_push(i * 3, x);
pq.set_op_push(i * 3 + 1, y);
pq.set_op_pop(i * 3 + 2);
}
long long minsum = pq.all_prod(), mini = N;
for (int i = 0; i < M - 1; i++) {
int x = A[N - 2 * i - 1], y = A[N - 2 * i - 2];
pq.set_op_null(i * 3 + 2);
pq.set_op_null(i * 3 + 1);
pq.set_op_null(i * 3);
pq.set_op_push(3 * M + i * 3, x);
pq.set_op_push(3 * M + i * 3 + 1, y);
pq.set_op_pop(3 * M + i * 3 + 2);
if (minsum > pq.all_prod()) {
minsum = pq.all_prod();
mini = 2 * (i + 1);
}
}
std::cout << N - mini << " " << sum - minsum << '\n';
}