Advertisement
cosenza987

Untitled

Jun 24th, 2023
744
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. template <class T> struct FenwickTree {
  8.     vector<T> fwt;
  9.     int n;
  10.     FenwickTree(int n_) {
  11.         n = n_;
  12.         fwt.assign(n, 0);
  13.     }
  14.     FenwickTree(vector<T>& a) {
  15.         n = (int)a.size();
  16.         fwt.assign(n, 0);
  17.         for (int i = 0; i < (int)a.size(); i++) {
  18.             add(i, a[i]);
  19.         }
  20.     }
  21.     T sum(int r) {
  22.         T ret = 0;
  23.         for (; r >= 0; r = (r & (r + 1)) - 1) {
  24.             ret += fwt[r];
  25.         }
  26.         return ret;
  27.     }
  28.     T query(int l, int r) {
  29.         if (l > r) {
  30.             return 0;
  31.         }
  32.         return sum(r) - sum(l - 1);
  33.     }
  34.     void add(int idx, T delta) {
  35.         for (; idx < n; idx = idx | (idx + 1)) {
  36.             fwt[idx] += delta;
  37.         }
  38.     }
  39. };
  40.  
  41. int main() {
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(nullptr);
  44.     int n;
  45.     cin >> n;
  46.     vector<int> v(n);
  47.     FenwickTree<int> fwt(n);
  48.     for(int i = 0; i < n; i++) {
  49.         cin >> v[i];
  50.     }
  51.     for(int i = 0; i < n; i++) {
  52.         cout << v[i] - fwt.sum(v[i] - 1) << " \n"[i == n - 1];
  53.         fwt.add(v[i] - 1, 1);
  54.     }
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement