Last active
January 22, 2016 17:27
-
-
Save Noobgam/0385cf58b15435481abb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment