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. segtree query(int node, int start, int end, int l, int r)
  68. {
  69.     segtree ans;
  70. 	if(r<start || end<l) return ans;		//range of node is completely outside given range
  71. 	if(l<=start && end<=r) return tree[node];		// range of node is completely inside given range
  72.  
  73. 	int mid = (start+end)/2;		//range of node is partially inside and partially outside the given range
  74. 	segtree p1 = query(2*node, start, mid, l, r);
  75. 	segtree p2 = query(2*node+1, mid+1, end, l, r);
  76.  
  77.     merge(p1.elems.begin(), p1.elems.end(), p2.elems.begin(), p2.elems.end(), back_inserter(ans.elems));
  78.     return ans;
  79. }
  80.  
  81.  
  82.  
  83.  
  84.  
  85. void solve()
  86. {
  87. 	cin>>n;
  88. 	rep(i,1,n+1) cin>>arr[i];
  89. 	build(1,1,n);
  90. 	cin>>q;
  91. 	int last_ans = 0;
  92. 	rep(i1,1,q+1)
  93. 	{
  94. 	    int a, b;
  95. 	    ll c;
  96. 		cin>>a>>b>>c;
  97. 		int i = a^last_ans;
  98. 		int j = b^last_ans;
  99. 		ll k = c^last_ans;
  100. 		if(i<1) i=1;
  101. 		if(j>n) j=n;
  102. 		if(i>j)
  103. 		{
  104. 		    last_ans = 0;
  105. 		    cout<<last_ans<<endl;
  106. 		    continue;
  107. 		}
  108. 		segtree ans = query(1,1,n,i,j);
  109. 		last_ans = (int)(ans.elems.size() - (upper_bound(ans.elems.begin(), ans.elems.end(), k)-ans.elems.begin()));
  110. 		cout<<last_ans<<endl;
  111. 	}
  112.  
  113. }
  114.  
  115.  
  116. int main()
  117. {
  118. 	ios_base::sync_with_stdio(false);
  119. 	cin.tie(0);
  120. 	cout.tie(0);
  121. 	int t=1;
  122. //	cin>>t;
  123. 	while(t--){
  124. 		solve();
  125. 	}
  126. 	return 0;
  127. }
Success #stdin #stdout 0.03s 96828KB
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/IOhbb2
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!