From 2f83962f1799e94c8108c575d1c0d35868b06c4e Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
Date: Thu, 8 Apr 2021 15:00:33 +0200
Subject: Pracownia 4 aisd

---
 Semestr 4/aisd/pracownia4/rozw.cpp | 126 ++++++++++++++++++++++++-------------
 1 file changed, 81 insertions(+), 45 deletions(-)

(limited to 'Semestr 4/aisd/pracownia4/rozw.cpp')

diff --git a/Semestr 4/aisd/pracownia4/rozw.cpp b/Semestr 4/aisd/pracownia4/rozw.cpp
index b3f97c8..9c314e2 100644
--- a/Semestr 4/aisd/pracownia4/rozw.cpp	
+++ b/Semestr 4/aisd/pracownia4/rozw.cpp	
@@ -1,8 +1,10 @@
 #include <bits/stdc++.h>
 using namespace std;
+typedef long long ll;
 
-const int M = (1<<20);
-const size_t size = M*2 + 10;
+const int K = 20;
+const int M = (1<<K);
+const size_t tree_size = M*2 + 10;
 
 struct query {
     char type;
@@ -16,14 +18,22 @@ struct query {
             int to;
         } sum;
         int del;
-    };
+    } info;
 };
 
-struct segtreePS {
-    int tree[size];
+struct kox_set {
+    ll tree[tree_size];
 
-    segtreePS() {
-        for (int i = 0; i < size; i++) tree[i] = 0;
+    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) {
@@ -34,10 +44,10 @@ struct segtreePS {
         }
     }
 
-    int query(int from, int to) {
+    ll sum(int from, int to) {
         from += M;
         to += M;
-        int ans = tree[from];
+        ll ans = tree[from];
         if (from != to) ans += tree[to];
         while (from/2 != to/2) {
             if (from % 2 == 0)  ans += tree[from + 1];
@@ -46,76 +56,102 @@ struct segtreePS {
         }
         return ans;
     }
-};
-
-struct segtreeSP {
-    int tree[size];
-
-    segtreeSP() {
-        for (int i = 0; i < size; i++) tree[i] = 0;
-    }
 
-    void update(int from, int to, int val) {
-        from += M;
-        to += M;
-        tree[from] += val;
-        if (from != val) tree[to] += val;
-        while (from/2 != to/2) {
-            if (from % 2 == 0)  tree[from + 1] += val;
-            if (to % 2 == 1)    tree[to - 1] += val;
-            to /= 2; from /= 2;
+    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;
     }
 
-    int query(int where) {
-        int ans = 0;
-        where += M;
-        while (where) {
-            ans += tree[where];
-            where /= 2;
+    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];
+            }
         }
-        return ans;
     }
 };
 
 vector<query> queries;
-segtreeSP sptree;
 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;
-        scanf(" %c", &c);
         if (c == 'D') {
             int a;
-            cin >> a;
-            q.del = a;
+            scanf("%d", &a);
+            pstree.add(a);
+            q.info.del = a;
         }
         else {
             int a, b;
-            cin >> a >> b;
+            scanf("%d%d", &a, &b);
             q.type = c;
             if (c == 'I') {
-                q.insert = {a, b};
+                q.info.insert = {a, b};
                 inserts++;
             } else {
-                q.sum = {a, b};
+                q.info.sum = {a, b};
             }
         }
         queries.push_back(q);
     }
-    for (int i = n-1; i > 0; i--) {
+
+    secik.fill(1);
+    for (int i = n-1; i >= 0; i--) {
         query q = queries[i];
-        if (q.type != 'I') continue;
-        int addition = sptree.query(q.insert.p);
-        q_to_pos[i] = addition + q.insert.p; 
+        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
-- 
cgit v1.2.3