test/PersistentQueue.test.cpp

• View this file on GitHub
• Last update: 2021-04-06 14:24:56+09:00
• Problem: https://judge.yosupo.jp/problem/persistent_queue

Depends on

• DataStructure/PersistentArray.cpp
• DataStructure/PersistentQueue.cpp

Code

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

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

	int q;
	cin >> q;
	vector<PersistentQueue<int>> s(q + 1);
	for (int i = 1; i <= q; ++i) {
		int com, t;
		cin >> com >> t;
		++t;
		if (com == 0) {
			int x;
			cin >> x;
			s[i] = s[t].push(x);
		} else {
			cout << s[t].front() << endl;
			s[i] = s[t].pop();
		}
	}
}

#line 1 "test/PersistentQueue.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_queue"
#line 2 "DataStructure/PersistentArray.cpp"
#include <array>
#include <vector>
#include <memory>

template <class T, std::size_t LOG> class PersistentArray {
public:
	using value_type = T;
	using const_reference = const value_type&;
	static constexpr std::size_t CHILD_SIZE = 1 << LOG;

private:
	struct node_type;
	using node_ptr = std::shared_ptr<node_type>;
	struct node_type {
		value_type value;
		std::array<node_ptr, CHILD_SIZE> child;
	};

	static value_type get(std::size_t i, node_ptr p) {
		if (!p) {
			return value_type();
		} else if (i == 0) {
			return p->value;
		} else {
			return get(i >> LOG, p->child[i & (CHILD_SIZE - 1)]);
		}
	}
	static node_ptr set(std::size_t i, const_reference val, node_ptr p) {
		node_ptr result = p ? std::make_shared<node_type>(*p) : std::make_shared<node_type>();
		if (i == 0) {
			result->value = val;
		} else {
			std::size_t index = i & (CHILD_SIZE - 1);
			result->child[index] = set(i >> LOG, val, result->child[index]);
		}
		return result;
	}
	static void destructive_set(std::size_t i, const_reference val, node_ptr& p) {
		if (!p) {
			p = std::make_shared<node_type>();
		}
		if (i == 0) {
			p->value = val;
		} else {
			std::size_t index = i & (CHILD_SIZE - 1);
			destructive_set(i >> LOG, val, p->child[index]);
		}
	}

	node_ptr root;
	PersistentArray(node_ptr _root) : root(_root) {}

public:
	PersistentArray() : root() {}
	PersistentArray(const std::vector<value_type>& v) : root() {
		for (std::size_t i = 0; i < v.size(); ++i) {
			destructive_set(i, v[i]);
		}
	}
	value_type get(std::size_t i) const {
		return get(i, root);
	}
	value_type operator[](std::size_t i) const {
		return get(i);
	}
	std::vector<value_type> to_a(std::size_t n) const {
		std::vector<value_type> result(n);
		for (std::size_t i = 0; i < n; ++i) {
			result[i] = get(i);
		}
		return result;
	}
	PersistentArray set(std::size_t i, const_reference val) const {
		return PersistentArray(set(i, val, root));
	}
	void destructive_set(std::size_t i, const_reference val) {
		destructive_set(i, val, root);
	}
};
#line 3 "DataStructure/PersistentQueue.cpp"
#include <cassert>

template <class T> class PersistentQueue {
public:
	using value_type = T;
	using data_type = PersistentArray<value_type, 2>;

private:
	data_type data;
	size_t begin, end;  // [begin, end)
	PersistentQueue(const data_type& _data, size_t _begin, size_t _end)
	    : data(_data), begin(_begin), end(_end) {}

public:
	PersistentQueue() : data(), begin(0), end(0) {}
	bool empty() const {
		return begin == end;
	}
	size_t size() const {
		return end - begin;
	}
	value_type front() const {
		assert(!empty());
		return data[begin];
	}
	value_type back() const {
		assert(!empty());
		return data[end - 1];
	}
	value_type operator[](size_t i) const {
		assert(i < size());
		return data[begin + i];
	}
	value_type at(size_t i) const {
		return operator[](i);
	}
	PersistentQueue push(const T& val) const {
		return PersistentQueue(data.set(end, val), begin, end + 1);
	}
	PersistentQueue pop() const {
		assert(!empty());
		return PersistentQueue(data.set(begin, value_type()), begin + 1, end);
	}
};
#line 3 "test/PersistentQueue.test.cpp"
#include <iostream>
#line 5 "test/PersistentQueue.test.cpp"
using namespace std;

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

	int q;
	cin >> q;
	vector<PersistentQueue<int>> s(q + 1);
	for (int i = 1; i <= q; ++i) {
		int com, t;
		cin >> com >> t;
		++t;
		if (com == 0) {
			int x;
			cin >> x;
			s[i] = s[t].push(x);
		} else {
			cout << s[t].front() << endl;
			s[i] = s[t].pop();
		}
	}
}

Back to top page