fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define str string
  3. #define ll long long
  4. #define db double
  5. #define pii pair<int, int>
  6. #define piii pair<int, pii>
  7. #define piiii pair<pii, pii>
  8. #define se second
  9. #define fi first
  10. #define vi vector<int>
  11. #define vii vector<vector<int>>
  12. #define mpii map<int, int>
  13. #define umpii unordered_map<int, int>
  14. #define si set<int>
  15. #define usa unordered_set<int>
  16. #define mulsi multiset<int>
  17. using namespace std;
  18.  
  19. const ll inf = 1e18 + 1;
  20. const int mod = 1e9 + 7;
  21. const int maxa = 5e4 + 5;
  22. const int maxn = 25e4 + 5;
  23. const int block = 505;
  24.  
  25. int bit[block][maxa], bit1[maxa];
  26. int n, q, a[maxn];
  27. ll sum;
  28.  
  29. void updatebit(int x, int k, int id){
  30. 	for(int i = k; i < maxa; i += i&-i)
  31. 		bit[id][i] += x;
  32. }
  33.  
  34. int getbit(int id, int x){
  35. 	int ret = 0;
  36. 	for(int i = x; i; i -= i&-i)
  37. 		ret += bit[id][i];
  38. 	return ret;
  39. }
  40.  
  41. void update(int x, int k, int v){
  42. 	for(int i = v; i < block; i += i&-i)
  43. 		updatebit(x, k, i);
  44. }
  45.  
  46. int get(int k, int x){
  47. 	int ret = 0;
  48. 	for(int i = k; i; i -= i&-i)
  49. 		ret += getbit(i, x);
  50. 	return ret;
  51. }
  52.  
  53. int main(){
  54. 	ios_base::sync_with_stdio(0);
  55. 	cin.tie(0); cout.tie(0);
  56. 	cin >> n;
  57. 	int sz = sqrt(n), num = ceil((1.0*n)/sz);
  58. 	for(int i = 0; i < n; ++i){
  59. 		cin >> a[i];
  60. 		update(1, a[i], i / sz + 1);
  61. 		for(int j = a[i] + 1; j < maxa; j += j&-j)
  62. 			sum += (ll)bit1[j];
  63. 		for(int j = a[i]; j; j -= j&-j)
  64. 			++bit1[j];
  65. 	}
  66. 	cin >> q;
  67. 	while(q--){
  68. 		int x, y; cin >> x >> y; --x;
  69. 		int j = x;
  70. 		while(--j >= 0 && !(j % sz == sz - 1))
  71. 			if(a[x] < a[j])
  72. 				--sum;
  73. 		if(j >= 0)
  74. 			sum -= (ll)(get(j / sz + 1, maxa - 1) - get(j / sz + 1, a[x]));
  75. 		j = x;
  76. 		while(++j < n && j % sz)
  77. 			if(a[j] < a[x])
  78. 				--sum;
  79. 		if(j < n)
  80. 			sum -= (ll)(get(num, a[x] - 1) - get(j / sz, a[x] - 1));
  81. 		j = x;
  82. 		while(--j >= 0 && !(j % sz == sz - 1))
  83. 			if(y < a[j])
  84. 				++sum;
  85. 		if(j >= 0)
  86. 			sum += (ll)(get(j / sz + 1, maxa - 1) - get(j / sz + 1, y));
  87. 		j = x;
  88. 		while(++j < n && j % sz)
  89. 			if(a[j] < y)
  90. 				++sum;
  91. 		if(j < n)
  92. 			sum += (ll)(get(num, y - 1) - get(j/sz, y - 1));
  93. 		cout << sum << '\n';
  94. 		update(-1, a[x], x/sz + 1);
  95. 		update(1, y, x/sz + 1);
  96. 		a[x] = y;
  97. 	}
  98. 	return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 15960KB
comments (?)
stdin
copy 
10
2 6 6 4 7 6 3 5 9 1 
7
8 8
5 1
5 6
10 5
7 1
10 10
4 6
stdout
copy 
17
18
16
13
14
8
6
https://ideone.com/waD1MO
language:
C++ (gcc 8.3)
created:
2 days 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!