fork(4) download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. inline int scan(){
  4. 	int x = 0;
  5. 	char c = getchar_unlocked();
  6. 	while(c < '0' || c > '9'){
  7. 		c = getchar_unlocked();
  8. 	}
  9. 	while(c >= '0' && c <= '9'){
  10. 		x = (x << 3) + (x << 1) + c - '0';
  11. 		c = getchar_unlocked();
  12. 	}
  13. 	return x;
  14. }
  15. const int N = 2.5e5 + 5;
  16. const int M = 5e4 + 5;
  17. const int SQN = 1005;
  18. int n;
  19. int arr[N];
  20. int q;
  21. int x , y;
  22. int start[SQN];
  23. int finish[SQN];
  24. int block[N];
  25. int bit[SQN][M] = {0};
  26. void update(int i , int idx , int val){
  27. 	while(idx < M){
  28. 		bit[i][idx] += val;
  29. 		idx += idx & -idx;
  30. 	}
  31. }
  32. int sum(int i , int idx){
  33. 	int res = 0;
  34. 	while(idx){
  35. 		res += bit[i][idx];
  36. 		idx -= idx & -idx;
  37. 	}
  38. 	return res;
  39. }
  40. long long inv = 0;
  41. int get(int l , int r , int x){
  42. 	int res = 0;
  43. 	for(int i = block[l] ; i <= block[r] ; ++i){
  44. 		if(start[i] >= l && finish[i] <= r){
  45. 			res += sum(i , x);
  46. 		}
  47. 		else{
  48. 			for(int j = max(start[i] , l) ; j <= min(finish[i] , r) ; ++j){
  49. 				res += (arr[j] <= x);
  50. 			}
  51. 		}
  52. 	}
  53. 	return res;
  54. }
  55. int main(){
  56. 	n = scan();
  57. 	for(int i = 1 ; i <= n ; ++i){
  58. 		//arr[i] = rand() % 50000;
  59. 		//++arr[i];
  60. 		arr[i] = scan();
  61. 	}
  62. 	int i = 1;
  63. 	int cur = 0;
  64. 	while(i <= n){
  65. 		int j = i;
  66. 		start[++cur] = i;
  67. 		while(j <= n && j < i + SQN){
  68. 			block[j] = cur;
  69. 			update(cur , arr[j] , 1);
  70. 			++j;
  71. 		}
  72. 		finish[cur] = j - 1;
  73. 		i = j;
  74. 	}
  75. 	for(int i = n ; i >= 1 ; --i){
  76. 		inv += sum(0 , arr[i] - 1);
  77. 		update(0 , arr[i] , 1);
  78. 	}
  79. 	q = scan();
  80. 	while(q--){
  81. 		//x = rand() % n;
  82. 		//++x;
  83. 		//y = rand() % 50000;
  84. 		//++y;
  85. 		x = scan() , y = scan();
  86. 		inv -= x - 1 - get(1 , x - 1 , arr[x]);
  87. 		inv -= get(x + 1 , n , arr[x] - 1);
  88. 		update(block[x] , y , 1);
  89. 		update(block[x] , arr[x] , -1);
  90. 		arr[x] = y;
  91. 		inv += x - 1 - get(1 , x - 1 , arr[x]);
  92. 		inv += get(x + 1 , n , arr[x] - 1);
  93. 		printf("%lld\n" , inv);
  94. 	}
  95. }
Time limit exceeded #stdin #stdout 5s 201664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D2bFGH
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!