test/yosupo/persistent_queue.test.cpp

View this file on GitHub
Last update: 2024-01-07 20:49:49+09:00
Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#include "../../data-structure/persistent_queue.hpp"

#include <bits/stdc++.h>
using namespace std;

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

    int Q;
    cin >> Q;
    PersistentQueue<int> init;
    vector<PersistentQueue<int>> ver(Q);
    for (int i = 0; i < Q; ++i) {
        int q, t;
        cin >> q >> t;
        if (q == 0) {
            int x;
            cin >> x;
            if (t == -1)
                ver[i] = init.push(x);
            else
                ver[i] = ver[t].push(x);
        } else {
            cout << ver[t].front() << "\n";
            ver[i] = ver[t].pop();
        }
    }
}

#line 1 "test/yosupo/persistent_queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"

#line 2 "data-structure/persistent_queue.hpp"
#include <cassert>

#line 2 "data-structure/persistent_array.hpp"
#include <memory>
#include <vector>

template <typename T, int B = 2>
class PersistentArray {
   public:
    PersistentArray() = default;
    explicit PersistentArray(const std::vector<T>& v) {
        for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]);
    }

    T get(int k) const { return get(root, k); }

    PersistentArray set(int k, const T& x) const {
        return PersistentArray(set(root, k, x));
    }

   private:
    struct Node;
    using node_ptr = std::shared_ptr<Node>;

    struct Node {
        T val;
        node_ptr ch[B];
    };

    node_ptr root = nullptr;

    explicit PersistentArray(const node_ptr& root) : root(root) {}

    T get(const node_ptr& t, int k) const {
        if (k == 0) return t->val;
        return get(t->ch[k % B], k / B);
    }

    node_ptr set(const node_ptr& t, int k, const T& x) const {
        node_ptr res =
            t ? std::make_shared<Node>(*t) : std::make_shared<Node>();
        if (k == 0) {
            res->val = x;
        } else {
            res->ch[k % B] = set(res->ch[k % B], k / B, x);
        }
        return res;
    }
};
#line 5 "data-structure/persistent_queue.hpp"

template <typename T>
class PersistentQueue {
   public:
    PersistentQueue() : first(0), last(0) {}

    int size() const { return last - first; }

    bool empty() const { return size() == 0; }

    T front() const {
        assert(!empty());
        return pa.get(first);
    }

    T back() const {
        assert(!empty());
        return pa.get(last - 1);
    }

    PersistentQueue push(const T& val) const {
        return PersistentQueue(pa.set(last, val), first, last + 1);
    }

    PersistentQueue pop() const {
        assert(!empty());
        return PersistentQueue(pa, first + 1, last);
    }

   private:
    PersistentArray<T> pa;
    int first, last;

    PersistentQueue(const PersistentArray<T>& pa, int first, int last)
        : pa(pa), first(first), last(last) {}
};
#line 4 "test/yosupo/persistent_queue.test.cpp"

#include <bits/stdc++.h>
using namespace std;

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

    int Q;
    cin >> Q;
    PersistentQueue<int> init;
    vector<PersistentQueue<int>> ver(Q);
    for (int i = 0; i < Q; ++i) {
        int q, t;
        cin >> q >> t;
        if (q == 0) {
            int x;
            cin >> x;
            if (t == -1)
                ver[i] = init.push(x);
            else
                ver[i] = ver[t].push(x);
        } else {
            cout << ver[t].front() << "\n";
            ver[i] = ver[t].pop();
        }
    }
}