aboutsummaryrefslogtreecommitdiff
path: root/Semestr 4/aisd/pracownia4
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2021-04-17 17:31:46 +0200
committerFranciszek Malinka <franciszek.malinka@gmail.com>2021-04-17 17:31:46 +0200
commita11df2c963520c64768158c2753237152a1eae3d (patch)
tree2e96c294b0955680a76d4f1f95a1be297c9dcb0f /Semestr 4/aisd/pracownia4
parent827657c21afae72288ff63254643a465682eb521 (diff)
Update
Diffstat (limited to 'Semestr 4/aisd/pracownia4')
-rw-r--r--Semestr 4/aisd/pracownia4/rozw2.cpp135
1 files changed, 135 insertions, 0 deletions
diff --git a/Semestr 4/aisd/pracownia4/rozw2.cpp b/Semestr 4/aisd/pracownia4/rozw2.cpp
new file mode 100644
index 0000000..17562a9
--- /dev/null
+++ b/Semestr 4/aisd/pracownia4/rozw2.cpp
@@ -0,0 +1,135 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+struct treap {
+ typedef long long T;
+ treap *left = nullptr;
+ treap *right = nullptr;
+ int rank, items = 1;
+ T value;
+ T sum;
+ bool rev = false;
+
+ treap(T val = T()) : rank(rand()), value(val), sum(val) {}
+
+ inline void update() {
+ if (rev) {
+ swap(left, right);
+ if (left) left->rev = !left->rev;
+ if (right) right->rev = !right->rev;
+ rev = false;
+ }
+ }
+};
+
+inline int items(treap *t) { return t ? t->items : 0; }
+inline int sum(treap *t) { return t ? t->sum : 0; }
+inline void recalc(treap *t) {
+ t->items = items(t->left) + items(t->right) + 1;
+ t->sum = sum(t->left) + sum(t->right) + t->value;
+}
+
+pair<treap*, treap*> split(treap *t, int k) {
+ if (!t) return {nullptr, nullptr};
+ t->update();
+ if (items(t->left) < k) {
+ auto p = split(t->right, k - items(t->left) - 1);
+ t->right = p.first;
+ recalc(t);
+ return {t, p.second};
+ }
+ else {
+ auto p = split(t->left, k);
+ t->right = p.first;
+ recalc(t);
+ return {p.first, t};
+ }
+}
+
+treap* merge(treap *a, treap *b) {
+ if (!a) return b;
+ if (!b) return a;
+ a->update();
+ b->update();
+ if (a->rank > b->rank) {
+ a->right = merge(a->right, b);
+ recalc(a);
+ return a;
+ }
+ else {
+ b->left = merge(a, b->left);
+ recalc(b);
+ return b;
+ }
+}
+
+treap::T select(treap *t, int k) {
+ if (!t) return treap::T();
+ t->update();
+ int i = items(t->left);
+ if (i == k) return t->value;
+ else if (i > k) return select(t->left, k);
+ else return select(t->right, k - i - 1);
+}
+
+treap *insert (treap *t, treap::T val, int k) {
+ auto p = split(t, k);
+ return merge(merge(p.first, new treap(val)), p.second);
+}
+
+treap *erase(treap *t, int k) {
+ auto p1 = split(t, k);
+ auto p2 = split(p1.second, 1);
+ return merge(p1.first, p2.second);
+}
+
+treap::T sum(treap *t, int l, int r) {
+ auto p1 = split(t, r);
+ auto p2 = split(p1.first, l);
+ return sum(p2.second);
+}
+
+void write(treap *t) {
+ if (!t) return;
+ t->update();
+ write(t->left);
+ cout << t->value << " ";
+ write(t->right);
+}
+void destroy(treap *t) {
+ if (!t) return;
+ destroy(t->left);
+ destroy(t->right);
+ delete t;
+}
+
+treap *t = 0;
+
+int main() {
+ int n;
+ scanf("%d", &n);
+ for (int i = 0; i < n; i++) {
+ char c;
+ scanf(" %c", &c);
+ if (c == 'I') {
+ int p, x;
+ scanf("%d%d", &p, &x);
+ t = insert(t, x, p);
+ }
+ if (c == 'D') {
+ int p;
+ scanf("%d", &p);
+ t = erase(t, p - 1);
+ }
+ if (c == 'S') {
+ int l, r;
+ scanf("%d%d", &l, &r);
+ printf("ans: %lld\n", sum(t, l, r));
+ }
+ cout << "Treap:\n";
+ write(t);
+ cout << "\n";
+ }
+
+ destroy(t);
+} \ No newline at end of file