data_structure/test/persistent_queue.test.cpp

• View this file on GitHub
• Last update: 2021-02-26 23:47:50+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

• data_structure/persistent_queue.hpp

Code

#include "../persistent_queue.hpp"
#include <iostream>
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    persistent_queue<int, 18> pq;
    int Q;
    cin >> Q;
    while (Q--) {
        int q, t;
        cin >> q >> t;
        if (q == 0) {
            int x;
            cin >> x;
            pq.push(t + 1, x);
        } else {
            cout << pq.pop(t + 1).second << '\n';
        }
    }
}

#line 2 "data_structure/persistent_queue.hpp"
#include <array>
#include <cassert>
#include <utility>
#include <vector>

// CUT begin
// Fully persistent queue
template <typename T, int D> struct persistent_queue {
    int now;

    std::vector<T> data;                 // Elements on each node of tree
    std::vector<std::array<int, D>> par; // binary-lifted parents
    std::vector<int> back_id;            // back_id[t] = leaf id of the tree at time t
    std::vector<int> size;               // size[t] = size of the queue at time t

    persistent_queue() : now(0), data(1), par(1), back_id(1, 0), size(1, 0) {}

    // Complexity: O(lgD)
    // return: (curret_time, popped element)
    std::pair<int, T> pop(int t) {
        now++;
        assert(now < 1 << (D + 1));
        int r = back_id[t], len = size[t] - 1;
        back_id.emplace_back(r), size.emplace_back(len);
        for (int d = 0; d < D; d++)
            if ((len >> d) & 1) r = par[r][d];
        return std::make_pair(now, data[r]);
    }

    // Complexity: O(lgD)
    // return: curret_time
    int push(int t, const T &dat) {
        now++;
        assert(now < 1 << (D + 1));
        int newid = data.size();
        data.emplace_back(dat);
        par.push_back({}), par.back()[0] = back_id[t];
        back_id.emplace_back(newid), size.emplace_back(size[t] + 1);
        for (int d = 1; d < D; d++) par[newid][d] = par[par[newid][d - 1]][d - 1];
        return now;
    }
};
#line 2 "data_structure/test/persistent_queue.test.cpp"
#include <iostream>
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    persistent_queue<int, 18> pq;
    int Q;
    cin >> Q;
    while (Q--) {
        int q, t;
        cin >> q >> t;
        if (q == 0) {
            int x;
            cin >> x;
            pq.push(t + 1, x);
        } else {
            cout << pq.pop(t + 1).second << '\n';
        }
    }
}

Back to top page