fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <map>
  4. #include <climits>
  5. using namespace std;
  6. template <class T>
  7. class FenwickTree{
  8. private:
  9.     unordered_map<long long, T> v;
  10.     long long ma;
  11.     long long mi;
  12. public:
  13.     FenwickTree(int max = INT_MAX, int min = 1) : ma(max), mi(min-1L) {}
  14.     void set(long long i, T d){
  15.         if(i<=mi||i>ma) throw "bad_allocation";
  16.         i -= mi;
  17.         while(i<=ma-mi){
  18.             v[i] += d;
  19.             i += i&-i;
  20.         }
  21.     }
  22.     T get(long long i){
  23.         if(i<=mi)   return NULL;
  24.         if(i>ma)    i = ma;
  25.         i -= mi;
  26.         T x = NULL;
  27.         while(i){
  28.             x += v[i];
  29.             i -= i&-i;
  30.         }
  31.         return x;
  32.     }
  33. };
  34. template <class T>
  35. class FenwickTree2 {
  36. private:
  37. 	int ma;
  38. 	int mi;
  39. 	FenwickTree<T> ft1;
  40. 	FenwickTree<T> ft2;
  41. public:
  42. 	FenwickTree2(int max = INT_MAX, int min = 1) : ft1(max,min), ft2(max,min), ma(max), mi(min) {}
  43. 	void set(long long l, long long r, T d){
  44. 		if(l>r)	throw "bad_allocation";
  45. 		ft1.set(l,d);
  46. 		ft2.set(l,d*(l-1));
  47. 		if(r==ma)	return;
  48. 		ft1.set(r+1,-d);
  49. 		ft2.set(r+1,-d*r);
  50. 	}
  51. 	void set(long long i, T d){
  52. 		set(i,i,d);
  53. 	}
  54. 	T get(long long i){
  55.         if(i>ma)    i = ma;
  56. 		return i*ft1.get(i) - ft2.get(i);
  57. 	}
  58. };
  59. class PrefixSum{
  60. private:
  61.     map<int, int> v;
  62. public:
  63.     void set(int i, int d){
  64.     	v[i] += d;
  65.     }
  66.     int get(int i){
  67.     	int x = 0;
  68.     	for(auto p: v)
  69.     		if(p.first>i)	break;
  70.     		else	x += p.second;
  71.     	return x;
  72.     }
  73. };
  74. int main() {
  75. 	int n,q,p;
  76. 	cin>>n>>q>>p;
  77. 	p %= 101;	// p: should be a percentage
  78. 	int offset = -50;
  79. 	FenwickTree2<int> ft(n-1+offset,offset);
  80. 	PrefixSum ps;
  81. 	int i,d;
  82. 	while(q--){
  83. 		i = offset+rand()%n;
  84. 		d = rand()%100;
  85. 		if(d<p){
  86. 			if(ft.get(i)!=ps.get(i))
  87. 				cout<<"Mismatch at i = "<<i<<" q = "<<q<<endl;
  88. 		}
  89. 		else{
  90. 			d = rand()%100;
  91. 			ft.set(i,d);
  92. 			ps.set(i,d);
  93. 		}
  94. 	}
  95. 	if(ft.get(n-1+offset)!=ps.get(n))
  96. 		cout<<"Final query mismatch"<<endl;
  97. 	else
  98. 		cout<<"Comparison finished"<<endl;
  99. 	return 0;
  100. }
Success #stdin #stdout 0.6s 4504KB
comments (?)
stdin
copy 
1000 1000000 10
stdout
copy 
Comparison finished
https://ideone.com/PdaqdH
Fenwick Tree for range updates
language:
C++14 (gcc 8.3)
created:
5 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!