fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iL0bIW
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!