From c5fcf7179a83ef65c86c6a4a390029149e518649 Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
Date: Tue, 5 Oct 2021 21:49:54 +0200
Subject: Duzy commit ze smieciami

---
 semestr-4/aisd/pracownia4/brut.cpp         |  69 +++++++++++++
 semestr-4/aisd/pracownia4/gen.py           |  24 +++++
 semestr-4/aisd/pracownia4/rozw.cpp         | 157 +++++++++++++++++++++++++++++
 semestr-4/aisd/pracownia4/rozw2.cpp        | 135 +++++++++++++++++++++++++
 semestr-4/aisd/pracownia4/rozw3.cpp        | 149 +++++++++++++++++++++++++++
 semestr-4/aisd/pracownia4/show_problem.pdf | Bin 0 -> 61345 bytes
 semestr-4/aisd/pracownia4/test.sh          |  21 ++++
 7 files changed, 555 insertions(+)
 create mode 100644 semestr-4/aisd/pracownia4/brut.cpp
 create mode 100644 semestr-4/aisd/pracownia4/gen.py
 create mode 100644 semestr-4/aisd/pracownia4/rozw.cpp
 create mode 100644 semestr-4/aisd/pracownia4/rozw2.cpp
 create mode 100644 semestr-4/aisd/pracownia4/rozw3.cpp
 create mode 100644 semestr-4/aisd/pracownia4/show_problem.pdf
 create mode 100755 semestr-4/aisd/pracownia4/test.sh

(limited to 'semestr-4/aisd/pracownia4')

diff --git a/semestr-4/aisd/pracownia4/brut.cpp b/semestr-4/aisd/pracownia4/brut.cpp
new file mode 100644
index 0000000..32f4ebb
--- /dev/null
+++ b/semestr-4/aisd/pracownia4/brut.cpp
@@ -0,0 +1,69 @@
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+struct insert_list {
+    vector<int> v;
+    
+    insert_list() {
+    }
+
+    void insert(int p, int val) {
+        assert(p <= v.size());
+        assert(p >= 0);
+        vector<int> temp;
+        for (int i = 0; i < p; i++) {
+            temp.push_back(v[i]);
+        }
+        temp.push_back(val);
+        for (int i = p; i < v.size(); i++) {
+            temp.push_back(v[i]);
+        }
+        v = temp;
+    }
+
+    void erase(int p) {
+        assert(p <= v.size());
+        assert(p >= 1);
+        vector<int> temp;
+        for (int i = 0; i < p-1; i++) {
+            temp.push_back(v[i]);
+        }
+        for (int i = p; i < v.size(); i++) {
+            temp.push_back(v[i]);
+        }
+        v = temp;
+    }
+
+    ll sum(int l, int r) {
+        ll ans = 0;
+        for (int i = l-1; i < r; i++) {
+            ans += v[i];
+        }
+        return ans;
+    }
+};  
+
+insert_list v;
+
+int main() {
+    ios_base::sync_with_stdio(false);
+    cin.tie();
+    int n;
+    cin >> n;
+    for (int i = 0; i < n; i++) {
+        char c;
+        cin >> c;
+        if (c == 'D') {
+            int a;
+            cin >> a;
+            v.erase(a);
+        }
+        else {
+            int a, b;
+            cin >> a >> b;
+            if (c == 'I') v.insert(a, b);
+            else cout << v.sum(a,b) << "\n";
+        }
+    }
+}
\ No newline at end of file
diff --git a/semestr-4/aisd/pracownia4/gen.py b/semestr-4/aisd/pracownia4/gen.py
new file mode 100644
index 0000000..733a60e
--- /dev/null
+++ b/semestr-4/aisd/pracownia4/gen.py
@@ -0,0 +1,24 @@
+from random import randint, seed, choice
+import sys
+
+
+seed(sys.argv[1])
+n = int(sys.argv[2])
+l = 0
+print(n)
+
+
+for i in range(n):
+    c = choice('ISD')
+    if l == 0:
+        c = 'I'
+
+    if c == 'D':
+        print(c, randint(1, l))
+        l -= 1
+    elif c == 'I':
+        print(c, randint(0, l), randint(-10, 10))
+        l += 1
+    else:
+        a = randint(1, l)
+        print(c, a, randint(a, l))
\ No newline at end of file
diff --git a/semestr-4/aisd/pracownia4/rozw.cpp b/semestr-4/aisd/pracownia4/rozw.cpp
new file mode 100644
index 0000000..9c314e2
--- /dev/null
+++ b/semestr-4/aisd/pracownia4/rozw.cpp
@@ -0,0 +1,157 @@
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+const int K = 20;
+const int M = (1<<K);
+const size_t tree_size = M*2 + 10;
+
+struct query {
+    char type;
+    union {
+        struct insert {
+            int p;
+            int x;
+        } insert;
+        struct sum {
+            int from;
+            int to;
+        } sum;
+        int del;
+    } info;
+};
+
+struct kox_set {
+    ll tree[tree_size];
+
+    kox_set() {
+        for (int i = 0; i < tree_size; i++) tree[i] = 0;
+    }
+
+    void add(int val) {
+        update(val, 1);
+    }
+
+    void del(int val) {
+        update(val, -1);
+    }
+
+    void update(int where, int val) {
+        where += M;
+        while (where) {
+            tree[where] += val;
+            where /= 2;
+        }
+    }
+
+    ll sum(int from, int to) {
+        from += M;
+        to += M;
+        ll ans = tree[from];
+        if (from != to) ans += tree[to];
+        while (from/2 != to/2) {
+            if (from % 2 == 0)  ans += tree[from + 1];
+            if (to % 2 == 1)    ans += tree[to - 1];
+            to /= 2; from /= 2;
+        }
+        return ans;
+    }
+
+    int kth_elem(int k) {
+        int where = 1;
+        while (where < M) {
+            where *= 2;
+            if (tree[where] < k) {
+                k -= tree[where];
+                where += 1;
+            } 
+        }
+        return where - M;
+    }
+
+    void fill(int value) {
+        for (int i = 0; i < M; i++) {
+            tree[i + M] = value;
+        }
+        for (int d = K-1; d >= 0; d--) {
+            int maks = (1<<d);
+            for (int i = 0; i < maks; i++) {
+                int ind = i + maks;
+                tree[ind] = tree[ind*2] + tree[ind*2 + 1];
+            }
+        }
+    }
+};
+
+vector<query> queries;
+map<int, int> q_to_pos;
+kox_set secik;
+kox_set pstree;
+
+
+int main() {
+    int n, inserts = 0;
+    scanf("%d", &n);
+    for (int i = 0; i < n; ++i) {
+        char c;
+        scanf(" %c", &c);
+        query q;
+        q.type = c;
+        if (c == 'D') {
+            int a;
+            scanf("%d", &a);
+            pstree.add(a);
+            q.info.del = a;
+        }
+        else {
+            int a, b;
+            scanf("%d%d", &a, &b);
+            q.type = c;
+            if (c == 'I') {
+                q.info.insert = {a, b};
+                inserts++;
+            } else {
+                q.info.sum = {a, b};
+            }
+        }
+        queries.push_back(q);
+    }
+
+    secik.fill(1);
+    for (int i = n-1; i >= 0; i--) {
+        query q = queries[i];
+        if (q.type == 'D') {
+            pstree.del(q.info.del);
+        }
+        if (q.type == 'I') {
+            int offset = pstree.sum(0, q.info.insert.p);
+            int kth = secik.kth_elem(q.info.insert.p + offset + 1);
+            secik.del(kth);
+            q_to_pos[i] = kth;
+            cout << q.info.insert.p << " " << offset << "\n";
+            cout << i << ": " << q_to_pos[i] << "\n";
+        }
+    }
+    secik.fill(0);
+    pstree.fill(0);
+
+    for (int i = 0; i < n; i++) {
+        query q = queries[i];
+        if (q.type == 'I') {
+            secik.add(q_to_pos[i]);
+            pstree.update(q_to_pos[i], q.info.insert.x);
+            // cout << "Inserting " << q.info.insert.x << " to " << q_to_pos[i] << "\n";
+        }
+        if (q.type == 'D') {
+            int pos = secik.kth_elem(q.info.del);
+            // cout << "kth: " << q.info.del << " " << pos << "\n";
+            secik.del(pos);
+            pstree.update(pos, -pstree.tree[pos + M]);
+        }
+        if (q.type == 'S') {
+            int from = secik.kth_elem(q.info.sum.from);
+            int to = secik.kth_elem(q.info.sum.to);
+            printf("%lld\n", pstree.sum(from, to));
+        }   
+    }
+}
\ No newline at end of file
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
diff --git a/semestr-4/aisd/pracownia4/rozw3.cpp b/semestr-4/aisd/pracownia4/rozw3.cpp
new file mode 100644
index 0000000..ec107ef
--- /dev/null
+++ b/semestr-4/aisd/pracownia4/rozw3.cpp
@@ -0,0 +1,149 @@
+
+#include <bits/stdc++.h>
+using namespace std;
+
+struct treap
+{
+    typedef long long T;
+    treap *left = nullptr, *right = nullptr;
+    
+    int rank, items = 1;
+    bool rev = false;
+    T value, sum;
+    
+    treap(T val = T()) : value(val), sum(val), rank(rand()) { }
+    
+    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 treap::T 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) //dzieli na prefiks dlugosci k i reszte
+{
+    if(!t) return make_pair(nullptr, nullptr);
+    //t = new treap(*t); //odkomentowac zeby zrobic strukture trwala
+    t->update();
+    if(items(t->left) < k)
+    {
+        auto p = split(t->right, k - items(t->left) - 1);
+        t->right = p.first;
+        recalc(t);
+        return make_pair(t, p.second);
+    }
+    else
+    {
+        auto p = split(t->left, k);
+        t->left = p.second;
+        recalc(t);
+        return make_pair(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) //zwraca k-ty element
+{
+    if(!t) return treap::T();
+    t->update();
+    int i = items(t->left);
+    if(i == k) return t->value;
+    if(i > k) return select(t->left, k);
+    return select(t->right, k - i - 1);
+}
+
+treap* insert(treap *t, treap::T val, int k) //wstaw val na pozycje k (liczac od 0)
+{
+    auto p = split(t, k);
+    return merge(merge(p.first, new treap(val)), p.second);
+}
+void write(treap *t)
+{
+    if(!t) return;
+    t->update();
+    write(t->left);
+    cout << "(" << t->value << ", " << t->sum << ") ";
+    write(t->right);
+}
+
+treap* erase(treap *t, int k)
+{
+    auto p1 = split(t, k);
+    auto p2 = split(p1.second, 1);
+    return merge(p1.first, p2.second);
+}
+
+treap* reverse(treap *t, int a, int b) //odwroc przedzial <a, b)
+{
+    auto p1 = split(t, b);
+    auto p2 = split(p1.first, a);
+    if(p2.second) p2.second->rev = !p2.second->rev;
+    return merge(merge(p2.first, p2.second), p1.second);
+}
+
+treap::T sum(treap* t, int l, int r) {
+    auto p1 = split(t, r);
+    auto p2 = split(p1.first, l);
+    treap::T ret = sum(p2.second);
+    merge(merge(p2.first, p2.second), p1.second);
+    return ret;
+}
+
+treap *root = 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);
+            root = insert(root, x, p);
+        }
+        if (c == 'D') {
+            int p;
+            scanf("%d", &p);
+            root = erase(root, p - 1);
+        }
+        if (c == 'S') {
+            int l, r;
+            scanf("%d%d", &l, &r);
+            printf("%lld\n", sum(root, l - 1, r));
+        }
+        // cout << "Treap:\n";
+        // write(root);
+        // cout << "\n";
+    }
+
+}
\ No newline at end of file
diff --git a/semestr-4/aisd/pracownia4/show_problem.pdf b/semestr-4/aisd/pracownia4/show_problem.pdf
new file mode 100644
index 0000000..8a1c155
Binary files /dev/null and b/semestr-4/aisd/pracownia4/show_problem.pdf differ
diff --git a/semestr-4/aisd/pracownia4/test.sh b/semestr-4/aisd/pracownia4/test.sh
new file mode 100755
index 0000000..dc725ad
--- /dev/null
+++ b/semestr-4/aisd/pracownia4/test.sh
@@ -0,0 +1,21 @@
+#!/bin/bash
+
+make brut
+make rozw3
+
+
+for i in {1..10000}
+do
+    echo $i
+    python3 gen.py $i $1 > test.in
+    ./rozw3 < test.in > wa.out
+    ./brut < test.in > test.out
+
+    if diff -w test.out wa.out
+    then
+        echo ok
+    else
+        echo nieok
+        break
+    fi
+done
-- 
cgit v1.2.3