Advertisement
Guest User

Untitled

a guest
May 10th, 2019
533
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int N = 1e5 + 7;
  8.  
  9. int t[N];
  10.  
  11. void upd(int p, int x) {
  12.     for (; p < N; p = (p | (p + 1))) {
  13.         t[p] += x;
  14.     }
  15. }
  16.  
  17. int sum(int p) {
  18.     int res = 0;
  19.     for (; p >= 0; p = (p & (p + 1)) - 1) {
  20.         res += t[p];
  21.     }
  22.     return res;
  23. }
  24.  
  25. int main() {
  26.     ios::sync_with_stdio(0);
  27.     cin.tie(0);
  28.     vector <int> a = {1, 5, 2, 3, 2, 6};
  29.     int n = (int) a.size();
  30.     for (int i = 0; i < n; i++) {
  31.         cout << sum(a[i] - 1) << ' ';
  32.         upd(a[i], 1);
  33.     }
  34.     return 0;
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement