diff options
author | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-04-08 15:00:33 +0200 |
---|---|---|
committer | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-04-08 15:00:33 +0200 |
commit | 2f83962f1799e94c8108c575d1c0d35868b06c4e (patch) | |
tree | 9ef3e16d3e80c8e44e93694e262199d8d5e6e7dc /Semestr 4/aisd/pracownia4/rozw.cpp | |
parent | f64f7de412dd06affb0670831bdd117bde33a192 (diff) |
Pracownia 4 aisd
Diffstat (limited to 'Semestr 4/aisd/pracownia4/rozw.cpp')
-rw-r--r-- | Semestr 4/aisd/pracownia4/rozw.cpp | 126 |
1 files changed, 81 insertions, 45 deletions
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 |