fork download
copy 
  1.  
  2. //Segment tree approach to Range-sum and update query problem.
  3. //arr and tree are 1-indexed
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define ll          long long
  8. #define pb          push_back
  9. #define mp          make_pair
  10. #define pii         pair<int,int>
  11. #define vi          vector<int>
  12. #define all(a)      (a).begin(),(a).end()
  13. #define lol         1000000007
  14. #define endl        '\n'
  15. #define rep(i,a,b)	for(int i=a;i<b;i++)
  16. #define SIZE		1000005
  17. using namespace std;
  18.  
  19.  
  20.  
  21. void MOD(ll &x)
  22. {
  23. 	if (x >= lol) x -= lol;
  24. 	if (x < 0) x += lol;
  25. }
  26.  
  27.  
  28.  
  29. typedef struct segtree
  30. {
  31.     vector<ll> elems;
  32. }segtree;
  33.  
  34.  
  35.  
  36. ll arr[SIZE+5];
  37. segtree tree[4*SIZE+5];
  38. int n, q;
  39.  
  40.  
  41.  
  42.  
  43.  
  44. void build(int node, int start, int end)
  45. {
  46. 	if(start>end) return;
  47.  
  48. 	if(start==end)
  49. 	{
  50. 	    tree[node].elems.pb(arr[start]);
  51. 	}
  52. 	else
  53. 	{
  54. 		int mid = (start+end)/2;
  55. 		build(2*node, start, mid);
  56. 		build(2*node+1, mid+1, end);
  57.  
  58.         merge(tree[2*node].elems.begin(), tree[2*node].elems.end(), tree[2*node+1].elems.begin(), tree[2*node+1].elems.end(), back_inserter(tree[node].elems));
  59.  
  60. 	}
  61. }
  62.  
  63.  
  64.  
  65.  
  66.  
  67. int query(int node, int start, int end, int l, int r, ll k)
  68. {
  69. 	if(r<start || end<l) return 0;
  70. 	if(l<=start && end<=r) return (int)(tree[node].elems.size() - (upper_bound(tree[node].elems.begin(), tree[node].elems.end(), k)-tree[node].elems.begin()));
  71. 	int mid = (start+end)/2;
  72. 	int p1 = query(2*node, start, mid, l, r, k);
  73. 	int p2 = query(2*node+1, mid+1, end, l, r, k);
  74.  
  75.     //merge(p1.elems.begin(), p1.elems.end(), p2.elems.begin(), p2.elems.end(), back_inserter(ans.elems));
  76.     return p1+p2;
  77. }
  78.  
  79.  
  80.  
  81.  
  82.  
  83. void solve()
  84. {
  85. 	cin>>n;
  86. 	rep(i,1,n+1) cin>>arr[i];
  87. 	build(1,1,n);
  88. 	cin>>q;
  89. 	int last_ans = 0;
  90. 	rep(i1,1,q+1)
  91. 	{
  92. 	    int a, b;
  93. 	    ll c;
  94. 		cin>>a>>b>>c;
  95. 		int i = a^last_ans;
  96. 		int j = b^last_ans;
  97. 		ll k = c^last_ans;
  98. // 		if(i<1) i=1;
  99. // 		if(j>n) j=n;
  100. // 		if(i>j)
  101. // 		{
  102. // 		    last_ans = 0;
  103. // 		    cout<<last_ans<<endl;
  104. // 		    continue;
  105. // 		}
  106. 		last_ans = query(1,1,n,i,j,k);
  107. 		//last_ans = (int)(ans.elems.size() - (upper_bound(ans.elems.begin(), ans.elems.end(), k)-ans.elems.begin()));
  108. 		cout<<last_ans<<endl;
  109. 	}
  110.  
  111. }
  112.  
  113.  
  114. int main()
  115. {
  116. 	ios_base::sync_with_stdio(false);
  117. 	cin.tie(0);
  118. 	cout.tie(0);
  119. 	int t=1;
  120. //	cin>>t;
  121. 	while(t--){
  122. 		solve();
  123. 	}
  124. 	return 0;
  125. }
Success #stdin #stdout 0.05s 96728KB
comments (?)
stdin
copy 
6
8 9 3 5 1 9
5
2 3 5
3 3 7
0 0 11
0 0 2
3 7 4
stdout
copy 
1
1
0
0
2
https://ideone.com/wWUae6
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!