fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> pii;
  5.  
  6. int upLimit, sqN, BIT[32768] = {};
  7.  
  8. bool sortFunc(pii a, pii b) {
  9. 	if (a.first / sqN == b.first / sqN) {
  10. 		return a.second < b.second;
  11. 	}
  12. 	return a.first/sqN < b.first/sqN;
  13. }
  14. int query(int x) {
  15. 	int sum = 0;
  16. 	for (; x > 0; x -= (x&(-x))) {
  17. 		sum += BIT[x];
  18. 	}
  19. 	return sum;
  20. }
  21. void update(int x, int val) {
  22. 	for (; x <= upLimit; x += (x&(-x))) {
  23. 		BIT[x] += val;
  24. 	}
  25. }
  26. void print(vector<int> nums) {
  27. 	for (int num: nums) {
  28. 		cout<<num<<" ";
  29. 	}cout<<endl;
  30. }
  31. void solve(vector<int> nums, vector<pii> sortedQueries) {
  32. 	print(nums);
  33. 	int prevL = 1, prevR = 1, curInvs = 0;
  34. 	update(nums[1], 1);
  35. 	for (pii q: sortedQueries) {
  36. 		cout<<q.first<<" "<<q.second<<endl;
  37. 		while (prevL < q.first) {
  38. 			update(nums[prevL], -1);
  39. 			// ct of nums which are smaller than nums[prevL]
  40. 			curInvs -= (query(nums[prevL] - 1));
  41. 			prevL++;
  42. 		}
  43. 		while (prevL > q.first) {
  44. 			prevL--;
  45. 			update(nums[prevL], 1);
  46. 			curInvs += query(nums[prevL] - 1);
  47.  
  48. 		}
  49. 		while (prevR > q.second) {
  50. 			update(nums[prevR], -1);
  51. 			curInvs -= (query(upLimit) - query(nums[prevR]));
  52. 			prevR--;
  53. 		}
  54. 		while (prevR < q.second) {
  55. 			prevR++;
  56. 			update(nums[prevR], 1);
  57. 			curInvs += (query(upLimit) - query(nums[prevR]));
  58. 		}
  59. 		cout<<curInvs<<endl;
  60. 	}
  61. }
  62.  
  63. int main() {
  64. 	// your code goes here
  65. 	int n, num, l, r;
  66. 	cin>>n;
  67. 	upLimit = n;
  68. 	vector <int> nums(n+1);
  69. 	vector <pii> queries, mappedNums;
  70. 	for (int i = 0; i < n; i++) {
  71. 		cin>>num;
  72. 		mappedNums.push_back({num, i + 1});
  73. 	}
  74. 	sort(mappedNums.begin(), mappedNums.end());
  75. 	nums[0]=0;
  76. 	for (int i = 0; i < n; i++) {
  77. 		nums[mappedNums[i].second] = i + 1;
  78. 	}
  79.  
  80. 	sqN = sqrt(n);
  81. 	int q;
  82. 	cin >> q;
  83. 	while (q--) {
  84. 		cin >> l >> r;
  85. 		queries.push_back({l, r});
  86. 	}
  87. 	sort(queries.begin(), queries.end(), sortFunc);
  88. 	solve(nums, queries);
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 4880KB
comments (?)
stdin
copy 
5
1 4 3 2 5
4
1 5
2 4
3 3
4 5
stdout
copy 
0 1 4 3 2 5 
1 5
3
3 3
0
2 4
3
4 5
0
https://ideone.com/SGuQ24
language:
C++14 (gcc 8.3)
created:
3 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!