test/library_checker/data_structure/persistent_queue.test.cpp

View this file on GitHub
Last update: 2024-11-18 03:54:10+09:00
Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"
#include <iostream>

#include "../../../lib/data_structure/persistent_queue.hpp"

using namespace std;

int main(){
    int q; cin >> q;
    PersistentQueue<int> que(q + 1);
    while(q--){
        int num, t; cin >> num >> t;
        t++;
        if(num == 0){
            int x; cin >> x;
            que.push(x, t);
        }else{
            cout << que.top(t) << "\n";
            que.pop(t);
        }
    }
}

#line 1 "test/library_checker/data_structure/persistent_queue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"
#include <iostream>

#line 2 "lib/data_structure/persistent_queue.hpp"

/**
 * @brief Persistent Queue (永続キュー)
 */

#include <vector>

#line 2 "lib/data_structure/persistent_array.hpp"

/**
 * @brief Persistent Array (永続配列)
 */

#include <cstring>

template<typename T>
struct PersistentArray{
    struct Node{
        T data;
        Node *ch[20] = {};
    };
    Node *root = nullptr;

    PersistentArray() {}

    Node *get_root(){
        return root;
    }

    void destructive_set(const int i, const T &val, Node *&t){
        if(!t) t = new Node();
        if(i == 0){
            t->data = val;
        } else{
            destructive_set(i / 20, val, t->ch[i % 20]);
        }
    }

    Node *set(const int i, const T &val, Node *&t){
        Node *res = new Node();
        if(t){
            std::memcpy(res->ch, t->ch, sizeof(t->ch));
            res->data = t->data;
        }
        if(i == 0){
            res->data = val;
        } else{
            res->ch[i % 20] = set(i / 20, val, res->ch[i % 20]);
        }
        return res;
    }

    T get(const int i, Node *t){
        if(!t) return T();
        if(i == 0){
            return t->data;
        } else{
            return get(i / 20, t->ch[i % 20]);
        }
    }
};
#line 10 "lib/data_structure/persistent_queue.hpp"

template<typename T>
struct PersistentQueue{
    PersistentArray<T> data;
    using node = typename PersistentArray<T>::Node *;
    std::vector<node> nodes;
    std::vector<int> front, back;
    int nxt = 1;

    PersistentQueue(int N) : nodes(N), front(N), back(N){
        nodes[0] = data.get_root();
    }

    int size(const int t) const {
        return back[t] - front[t];
    }

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

    T top(const int t) {
        return data.get(front[t], nodes[t]);
    }

    int pop(const int t){
        nodes[nxt] = nodes[t];
        front[nxt] = front[t] + 1;
        back[nxt] = back[t];
        return nxt++;
    }

    int push(const T &x, const int t){
        nodes[nxt] = data.set(back[t], x, nodes[t]);
        front[nxt] = front[t];
        back[nxt] = back[t] + 1;
        return nxt++;
    }
};
#line 5 "test/library_checker/data_structure/persistent_queue.test.cpp"

using namespace std;

int main(){
    int q; cin >> q;
    PersistentQueue<int> que(q + 1);
    while(q--){
        int num, t; cin >> num >> t;
        t++;
        if(num == 0){
            int x; cin >> x;
            que.push(x, t);
        }else{
            cout << que.top(t) << "\n";
            que.pop(t);
        }
    }
}