treap.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
#include <map>

using namespace std;

const int maxn = (1e9) + 1;
const int maxq = 4e5;


struct treap
{
	struct node
	{
		node *l, *r;
		int prior;
		int size;
		int val;
		int cnt;
		int sum;
		node()
		{
			l = NULL;
			r = NULL;
		}
		node(node* a)
		{
			l = NULL;
			r = NULL;
			prior = a->prior;
			size = a->size;
			val = a->val;
			cnt = a->cnt;
		}
		node(int q)
		{
			l = NULL;
			r = NULL;
			size = 1;
			val = q;
			cnt = 1;
			sum = val;
			prior = rand();
		}
		node(int key, int prior1)
		{
			val = key;
			prior = prior1;
			l = NULL;
			r = NULL;
			size = 1;
			sum = val;
			cnt = 1;
		}
		void update()
		{
			size = cnt;
			sum = val;
			if (this->l != NULL)
				size += this->l->size, sum += this->l->sum;
			if (this->r != NULL)
				size += this->r->size, sum += this->r->sum;
		}
	};
	node* root;
	int size(node* i)
	{
		if (i == NULL)
			return 0;
		return i->size;
	}
	int sum(node* i)
	{
		if (i != NULL)
			return i->sum;
		return 0LL;
	}
	treap()
	{
		root = NULL;
	}
	node* merge(node* a, node *b)
	{
		if (a == NULL) return b;
		if (b == NULL) return a;
		if (a->prior > b->prior)
		{
			a->r = merge(a->r, b);
			a->update();
			return a;
		}
		else
		{
			b->l = merge(a, b->l);
			b->update();
			return b;
		}
	}
	pair <node*, node*> split(node* u, int key)
	{
		pair <node*, node*> l;
		if (u == NULL)
		{
			l.first = NULL;
			l.second = NULL;
			return l;
		}
		if (size(u->l) + 1 <= key)
		{
			pair <node*, node*> lr = split(u->r, key - size(u->l) - 1);
			u->r = lr.first;
			lr.first = u;
			u->update();
			return lr;
		}
		else
		{
			pair <node*, node*> lr = split(u->l, key);
			u->l = lr.second;
			lr.second = u;
			u->update();
			return lr;
		}
	}
	bool check(node* i, int key)
	{
		while (i != NULL)
		{
			if (i->val < key)
				i = i->r;
			else if (i->val > key)
				i = i->l;
			else if (i->val == key)
				return true;
		}
		return false;
	}
	node* insert(node* i, int key, int prior)
	{
		if (i == NULL)
			return new node(key, prior);
		if (i->prior < prior)
		{
			pair <node*, node*> lr = split(i, key);
			node *l = new node(key, prior);
			l->l = lr.first;
			l->r = lr.second;
			l->update();
			return l;
		}
		else
			if (i->val < key)
				i->r = insert(i->r, key, prior);
			else
				i->l = insert(i->l, key, prior);
		i->update();
		return i;
	}
	void insert(int f)
	{
		if (check(root, f))
		{
			node* i = root;
			while (i->val != f)
			{
				if (i->val < f)
					i->size++, i = i->r;
				if (i->val > f)
					i->size++, i = i->l;
			}
			i->cnt++;
			i->size++;
			return;
		}
		root = insert(root, f, rand());
	}
	int count(int f)
	{
		pair <node*, node*> l = split(root, f);
		pair <node*, node*> ab = split(l.first, f - 1);
		int cnt = size(ab.second);
		root = merge(merge(ab.first, ab.second), l.second);
		return cnt;
	}
	int order(int q)
	{
		pair <node*, node*> lr = split(root, q);
		int res = size(lr.first);
		root = merge(lr.first, lr.second);
		return res;
	}
	int between(int l, int r)
	{
		pair <node*, node*> lr = split(root, r);
		pair <node*, node*> ab = split(lr.first, l - 1);
		int res = size(ab.second);
		root = merge(merge(ab.first, ab.second), lr.second);
		return res;
	}
};



void print(treap::node* i)
{
	if (i == NULL)
		return;
	if (i->l != NULL)
		print(i->l);
	cerr << i->val << " ";
	if (i->r != NULL)
		print(i->r);
}

treap* oper = new treap();

struct node
{
	node *l, *r;
	treap i;
	node()
	{
		l = NULL;
		r = NULL;
	}
};

int A, B, X;

vector <treap::node*> took;

//To take whole level from all layers
//returns number of elements before the layer in treap so we can delete it properly

int cnt = 0;

int take(node* i, int l, int r)
{
	if (l == r)
	{
		if (X != 0)
			cnt = X;
		else
			cnt = oper->size(i->i.root);
		auto lr = i->i.split(i->i.root, cnt);
		i->i.root = lr.second;
		took.push_back(lr.first);
		return 0;
	}
	int m = (l + r) / 2;
	if (i->l == NULL)
		i->l = new node();
	if (i->r == NULL)
		i->r = new node();
	if (m >= A)
	{
		//fuck this.
		int keep = take(i->l, l, m);
		auto lr = i->i.split(i->i.root, keep);
		auto lr1 = i->i.split(lr.second, cnt);
		i->i.root = i->i.merge(lr.first, lr1.second);
		took.push_back(lr1.first);
		return keep;
	}
	else
	{
		int size_l = oper->size(i->l->i.root);
		int keep = take(i->r, m + 1, r);
		//REALLY
		auto lr = i->i.split(i->i.root, size_l + keep);
		auto lr1 = i->i.split(lr.second, cnt);
		i->i.root = i->i.merge(lr.first, lr1.second);
		took.push_back(lr1.first);
		return size_l + keep;
	}
}

//Transfer is working horribly wrong
//Think about it.
int transfer(node* i, int l, int r)
{
	if (l == r)
	{
		int sz = oper->size(i->i.root);
		i->i.root = i->i.merge(i->i.root, took.back());
		took.pop_back();
		return sz;
	}
	int m = (l + r) / 2;
	if (m >= B)
	{
		if (i->l == NULL)
			i->l = new node();
		//fuck this.
		int keep = transfer(i->l, l, m);
		auto lr = i->i.split(i->i.root, keep);
		i->i.root = i->i.merge(i->i.merge(lr.first, took.back()), lr.second);
		took.pop_back();
		return keep;
	}
	else
	{
		if (i->r == NULL)
			i->r = new node();
		//REALLY
		int size_l;
		if (i == NULL || i->l == NULL)
			size_l = 0;
		else
			size_l = oper->size(i->l->i.root);
		int keep = transfer(i->r, m + 1, r);
		auto lr = i->i.split(i->i.root, keep + size_l);
		i->i.root = i->i.merge(i->i.merge(lr.first, took.back()), lr.second);
		took.pop_back();
		return keep + size_l;
	}
}

//simply used in init function to insert X into every layer

int add(node* i, int l, int r)
{

	if (l == r)
	{
		i->i.root = i->i.merge(i->i.root, new treap::node(X));
		return oper->size(i->i.root) - 1;
	}
	int m = (l + r) / 2;
	if (m >= A)
	{
		if (i->l == NULL)
			i->l = new node();
		//fuck this.
		int keep = add(i->l, l, m);
		auto lr = i->i.split(i->i.root, keep);
		i->i.root = oper->merge(oper->merge(lr.first, new treap::node(X)), lr.second);
		return keep;
	}
	else
	{
		if (i->r == NULL)
			i->r = new node();
		int size_l;
		if (i == NULL || i->l == NULL)
			size_l = 0;
		else
			size_l = oper->size(i->l->i.root);
		int keep = add(i->r, m + 1, r);
		//REALLY
		auto lr = i->i.split(i->i.root, size_l + keep);
		i->i.root = oper->merge(oper->merge(lr.first, new treap::node(X)), lr.second);
		return size_l + keep;
	}
}

int get(node*i, int l, int r)
{
	if (r < A || l > B) return 0LL;
	if (l >= A && r <= B)
		return oper->sum(i->i.root);
	int cur = 0;
	if (i->l != NULL)
		cur += get(i->l, l, (l + r) / 2);
	if (i->r != NULL)
		cur += get(i->r, (l + r) / 2 + 1, r);
	return cur;
}

node* root = new node();

int main()
{
	int n;
	int k2 = 1;
	while (k2 < maxn)
		k2 <<= 1;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		A = a;
		X = b;
		add(root, 0, k2 - 1);
	}
	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		int query;
		scanf("%d", &query);
		if (query == 0)
		{
			scanf("%d %d", &A, &B);
			printf("%d\n", get(root, 0, k2 - 1));
			continue;
		}
		if (query == 1)
		{
			scanf("%d %d", &A, &B);
			X = 0;
			take(root, 0, k2 - 1);
			transfer(root, 0, k2 - 1);
			continue;
		}
		if (query == 2)
		{
			scanf("%d %d", &A, &X);
			take(root, 0, k2 - 1);
			took.clear();
			continue;
		}
	}
	return 0;
}