In the beginning of the system!

In the beginning of the system!

Eexplanation: Implicit cartesian tree in GNU C++ STL.

Topic: PBDS

	#include<bits/stdc++.h>
	#include<ext/rope> // header with rope
	using namespace std;
	using namespace __gnu_cxx; // namespace with rope and some additional stuff.
	int main()
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	///rope<int> v; // use as usual STL container.
	int n,m;
	cin >> n >> m;
	rope<int> v(n, 0);
	///for(int i = 1; i <= n; i++)
	for(int i = 0; i < n; i++)
	v.mutable_reference_at(i) = i + 1;
	/// v.push_back(i);
	int l,r;
	for(int i = 0; i < m; i++){
	cin >> l >> r;
	--l;
	--r;
	rope<int> cur = v.substr(l, r - l + 1); // range saved
	v.erase(l, r - l + 1); // range delete
	v.insert(v.mutable_begin(), cur);
	}
	/// rope<int>:: iterator it;
	/// for(it = v.mutable_begin(); it != v.mutable_end(); it++)
	///cout << *it << " ";
	for(int i = 0; i < n; i++)cout << v[i] << " ";
	return 0;
	}

view raw rope tree.cpp hosted with ❤ by GitHub

Share: