fork download
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. const int MAXN = (1 << 20);
  6.  
  7. template <class T>
  8. struct fenwick
  9. {
  10. int sz;
  11. vector<T> tr;
  12.  
  13. void init(int n)
  14. {
  15. sz = n + 1;
  16. tr.assign(sz + 2, 0);
  17. }
  18.  
  19. T query(int idx)
  20. {
  21. T ans = 0;
  22. for(; idx >= 1; idx -= (idx & -idx))
  23. ans += tr[idx];
  24. return ans;
  25. }
  26.  
  27. void update(int idx, T val)
  28. {
  29. if(idx <= 0) return;
  30. for(; idx <= sz; idx += (idx & -idx))
  31. tr[idx] += val;
  32. }
  33.  
  34. T query(int l, int r) { return query(r) - query(l - 1); }
  35. };
  36.  
  37. template<class T>
  38. struct compressed_fenwick
  39. {
  40. fenwick<T> t;
  41. vector<int> li;
  42.  
  43. int get_idx(int x) { return lower_bound(li.begin(), li.end(), x) - li.begin() + 1; }
  44. void update(int x, T val) { t.update(get_idx(x), val); }
  45.  
  46. void add_to_prep(int x) { li.push_back(x); }
  47. void prepare()
  48. {
  49. sort(li.begin(), li.end());
  50. li.erase(unique(li.begin(), li.end()), li.end());
  51. t.init(li.size() + 2);
  52. }
  53.  
  54. T query(int x) { return t.query(get_idx(x) - 1); }
  55. T size() { return t.query(t.sz); }
  56. };
  57.  
  58. void read()
  59. {
  60.  
  61. }
  62.  
  63. void solve()
  64. {
  65.  
  66. }
  67.  
  68. int main()
  69. {
  70. ios_base::sync_with_stdio(false);
  71. cin.tie(NULL);
  72.  
  73. read();
  74. solve();
  75. return 0;
  76. }
  77.  
Success #stdin #stdout 0s 16064KB
stdin
Standard input is empty
stdout
Standard output is empty