fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int arr[100000 + 5];
  4. int Index[100000 + 5];
  5. vector<int> ST[4 * 100000 + 5];
  6. bool cmp(int i, int j)
  7. {
  8. 	return arr[i] < arr[j];
  9. }
  10. void build(int start, int end,int pos)
  11. {
  12. 	if (start > end)return;
  13. 	if (start == end)
  14. 	{
  15. 		ST[pos].push_back(Index[start]);
  16. 		return;
  17. 	}
  18. 	int mid = (start + end) >> 1;
  19. 	build(start, mid, pos << 1);
  20. 	build(mid + 1, end, pos << 1 | 1);
  21. 	ST[pos].resize(ST[2 * pos].size() + ST[2 * pos + 1].size());
  22. 	merge(ST[2 * pos].begin(), ST[2 * pos].end(), ST[2 * pos + 1].begin(), ST[2 * pos + 1].end(), ST[pos].begin());
  23.  
  24. 	/*
  25. 		calculate prefix sum here !
  26. 		for(i in ST[pos])
  27. 		prefix[pos][i] = prefix[pos][i-1] + arr[ ST[pos][i-1] ];
  28.  
  29. 		note : here we are taking the prefix sum of values in our initial array with the help of arr[]
  30. 	*/
  31. }
  32.  int ans=0;
  33. int Query(int L,int R,int start, int end, int pos,int k)
  34. {
  35. 	if (start == end)
  36. 		return ST[pos][0];
  37. 	int lo = lower_bound(ST[2*pos].begin(), ST[2*pos].end(),L) - ST[2*pos].begin();
  38. 	int hi = upper_bound(ST[2*pos].begin(), ST[2*pos].end(), R) - ST[2*pos].begin();
  39. 	int x = hi - lo;
  40. 	int mid = (start + end) >> 1;
  41.  
  42. 	if (x >= k)
  43. 	{
  44. 		return Query(L, R, start, mid, 2 * pos, k);
  45. 	}
  46. 	else
  47. 	{
  48. 		k = k - x;
  49.  
  50. 		for (int i = lo; i < hi; ++i)
  51. 			ans+=arr[ST[2*pos][i]];  
  52. /* we can do prefix[2*pos][hi-1] - prefix[2*pos][lo-1], hi-1 bcz upper_bound will give one index higher
  53. */
  54.  
  55. 		return Query(L, R, mid + 1,end, 2 * pos + 1, k);
  56. 	}
  57. }
  58.  
  59.  
  60. int main()
  61. {
  62. 	int n, Q,L,R,k;
  63. 	scanf("%d%d", &n, &Q);
  64. 	for (int i = 1; i <= n; i++)
  65. 	{
  66. 		scanf("%d", arr + i);
  67. 		Index[i] = i;
  68. 	}
  69. 	sort(Index + 1, Index + 1 + n, cmp);
  70. 	build(1,n,1);
  71. 	while (Q--)
  72. 	{
  73. 		ans=0;
  74. 		scanf("%d%d%d", &L, &R, &k);
  75. 		int x= Query(L, R, 1, n, 1, k);
  76. 		printf("%d\n",ans+arr[x]);
  77. 	}
  78. 	return 0;
  79.  
  80. }
Success #stdin #stdout 0s 25400KB
comments (?)
stdin
copy 
6 4
5 1 7 4 6 3
2 5 3
6 6 1
1 6 5
3 6 1
stdout
copy 
11
3
19
3
https://ideone.com/uR9BKK
language:
C++14 (gcc 8.3)
created:
8 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!