fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 2.5e5 + 5;
  4. const int M = 5e4 + 5;
  5. const int SQN = 505;
  6. int n;
  7. int arr[N];
  8. int q;
  9. int x , y;
  10. int start[SQN];
  11. int finish[SQN];
  12. int block[N];
  13. int bit[SQN][M] = {0};
  14. void update(int i , int idx , int val){
  15. 	while(idx < M){
  16. 		bit[i][idx] += val;
  17. 		idx += idx & -idx;
  18. 	}
  19. }
  20. int sum(int i , int idx){
  21. 	int res = 0;
  22. 	while(idx){
  23. 		res += bit[i][idx];
  24. 		idx -= idx & -idx;
  25. 	}
  26. 	return res;
  27. }
  28. long long inv = 0;
  29. int get(int l , int r , int x){
  30. 	int res = 0;
  31. 	for(int i = block[l] ; i <= block[r] ; ++i){
  32. 		if(start[i] >= l && finish[i] <= r){
  33. 			res += sum(i , x);
  34. 		}
  35. 		else{
  36. 			for(int j = max(start[i] , l) ; j <= min(finish[i] , r) ; ++j){
  37. 				res += (arr[j] <= x);
  38. 			}
  39. 		}
  40. 	}
  41. 	return res;
  42. }
  43. int main(){
  44. 	scanf("%d" , &n);
  45. 	for(int i = 1 ; i <= n ; ++i){
  46. 		scanf("%d" , arr + i);
  47. 	}
  48. 	int i = 1;
  49. 	int cur = 0;
  50. 	while(i <= n){
  51. 		int j = i;
  52. 		start[++cur] = i;
  53. 		while(j <= n && j < i + SQN){
  54. 			block[j] = cur;
  55. 			update(cur , arr[j] , 1);
  56. 			++j;
  57. 		}
  58. 		finish[cur] = j - 1;
  59. 		i = j;
  60. 	}
  61. 	for(int i = n ; i >= 1 ; --i){
  62. 		inv += get(i + 1 , n , arr[i] - 1);
  63. 	}
  64. 	scanf("%d" , &q);
  65. 	while(q--){
  66. 		scanf("%d %d" , &x , &y);
  67. 		inv -= x - 1 - get(1 , x - 1 , arr[x]);
  68. 		inv -= get(x + 1 , n , arr[x] - 1);
  69. 		update(block[x] , y , 1);
  70. 		update(block[x] , arr[x] , -1);
  71. 		arr[x] = y;
  72. 		inv += x - 1 - get(1 , x - 1 , arr[x]);
  73. 		inv += get(x + 1 , n , arr[x] - 1);
  74. 		printf("%lld\n" , inv);
  75. 	}
  76. }
Success #stdin #stdout 0s 104000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8oySJD
language:
C++14 (gcc 8.3)
created:
8 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!