fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. struct trnode{
  4. 	trnode* left;
  5. 	trnode* right;
  6. 	int val;
  7. 	int pri;
  8. 	int siz;
  9. 	trnode(int _val){
  10. 		val = _val;
  11. 		pri = rand();
  12. 		siz = 1;
  13. 		left = NULL;
  14. 		right = NULL;
  15. 	}
  16. };
  17. typedef trnode* pnode;
  18. struct treap{
  19. 	pnode root;
  20. 	treap(){
  21. 		root = NULL;
  22. 	}
  23. 	int size(pnode tree){
  24. 		if(tree){
  25. 			return tree -> siz;
  26. 		}
  27. 		return 0;
  28. 	}
  29. 	void upd(pnode &tree){
  30. 		if(tree){
  31. 			tree -> siz = size(tree -> left) + 1 + size(tree -> right);
  32. 		}
  33. 	}
  34. 	void split(pnode tree , pnode &l , pnode &r , int key){
  35. 		if(!tree){
  36. 			l = NULL;
  37. 			r = NULL;
  38. 		}
  39. 		else if(tree -> val <= key){
  40. 			split(tree -> right , tree -> right , r , key);
  41. 			l = tree;
  42. 		}
  43. 		else{
  44. 			split(tree -> left , l , tree -> left , key);
  45. 			r = tree;
  46. 		}
  47. 		upd(tree);
  48. 	}
  49. 	void merge(pnode &tree , pnode l , pnode r){
  50. 		if(!l || !r){
  51. 			tree = l ? l : r;
  52. 		}
  53. 		else if(l -> pri > r -> pri){
  54. 			merge(l -> right , l -> right , r);
  55. 			tree = l;
  56. 		}
  57. 		else{
  58. 			merge(r -> left , l , r -> left);
  59. 			tree = r;
  60. 		}
  61. 		upd(tree);
  62. 	}
  63. 	void insert(pnode &tree , pnode key){
  64. 		if(!tree){
  65. 			tree = key;
  66. 		}
  67. 		else if(tree -> pri < key -> pri){
  68. 			split(tree , key -> left , key -> right , key -> val);
  69. 			tree = key;
  70. 		}
  71. 		else if(tree -> val >= key -> val){
  72. 			insert(tree -> left , key);
  73. 		}
  74. 		else{
  75. 			insert(tree -> right , key);
  76. 		}
  77. 		upd(tree);
  78. 	}
  79. 	void erase(pnode &tree , int key){
  80. 		if(!tree){
  81. 			return;
  82. 		}
  83. 		else if(tree -> val == key){
  84. 			merge(tree , tree -> left , tree -> right);
  85. 		}
  86. 		else if(tree -> val > key){
  87. 			erase(tree -> left , key);
  88. 		}
  89. 		else{
  90. 			erase(tree -> right , key);
  91. 		}
  92. 		upd(tree);
  93. 	}
  94. 	void erase(int key){
  95. 		erase(root , key);
  96. 	}
  97. 	void insert(int key){
  98. 		insert(root , new trnode(key));
  99. 	}
  100. 	int range(int l , int r){
  101. 		pnode L = NULL;
  102. 		pnode R = NULL;
  103. 		pnode X = NULL;
  104. 		pnode Y = NULL;
  105. 		split(root , L , R , r);
  106. 		split(L , X , Y , l - 1);
  107. 		int ret = size(Y);
  108. 		merge(L , X , Y);
  109. 		merge(root , L , R);
  110. 		return ret;
  111. 	}
  112. };
  113. const int N = 2.5e5 + 5;
  114. const int M = 5e4 + 5;
  115. const int LN = 15;
  116. int n;
  117. int arr[N];
  118. int q;
  119. int x , y;
  120. long long inv = 0;
  121. struct node{
  122.     treap indices;
  123.     int left;
  124.     int right;
  125.     node(){
  126.         left = -1;
  127.         right = -1;
  128.     }
  129. };
  130. struct TRIE{
  131. 	node nodes[(N + 10001) * LN];
  132.     int cur;
  133.     TRIE(){
  134.         cur = 0;
  135.     }
  136.     void insert(int num ,int index){
  137.     	int nd = 0;
  138.         for(int i = LN ; i >= 0 ; --i){
  139.             bool b = (num >> i) & 1;
  140.             if(b){
  141.                 if(nodes[nd].right == -1){
  142.                     nodes[nd].right = ++cur;
  143.                 }
  144.                 nd = nodes[nd].right;
  145.                 nodes[nd].indices.insert(index);
  146.             }
  147.             else{
  148.                 if(nodes[nd].left == -1){
  149.                     nodes[nd].left = ++cur;
  150.                 }
  151.                 nd = nodes[nd].left;
  152.                 nodes[nd].indices.insert(index);
  153.             }
  154.         }
  155.     }
  156.     void erase(int num , int index){
  157.         int nd = 0;
  158.         for(int i = LN ; i >= 0 ; --i){
  159.             bool b = (num >> i) & 1;
  160.             if(b){
  161.                 nd = nodes[nd].right;
  162.             }
  163.             else{
  164.                 nd = nodes[nd].left;
  165.             }
  166.             nodes[nd].indices.erase(index);
  167.         }
  168.     }
  169.     void update(int index , int value){
  170.     	erase(arr[index] , index);
  171.     	arr[index] = value;
  172.     	insert(arr[index] , index);
  173.     }
  174.     int get(int l , int r , int k){
  175.         ++k;
  176.         int ret = 0;
  177.         int nd = 0;
  178.         for(int i = LN ; i >= 0 && nd >= 0; --i){
  179.             bool b = (k >> i) & 1;
  180.             if(b){
  181.                 int z = 0;
  182.                 if(nodes[nd].left != -1){
  183.                 	z = nodes[nodes[nd].left].indices.range(l , r);
  184.                 }
  185.                 ret += z;
  186.                 nd = nodes[nd].right;
  187.             }
  188.             else{
  189.                 nd = nodes[nd].left;
  190.             }
  191.         }
  192.         return ret;
  193.     }
  194. };
  195. TRIE trie;
  196. int main(){
  197. 	scanf("%d" , &n);
  198. 	for(int i = 1 ; i <= n ; ++i){
  199. 		scanf("%d" , arr + i);
  200. 		trie.insert(arr[i] , i);
  201. 	}
  202. 	for(int i = n ; i >= 1 ; --i){
  203. 		inv += trie.get(i + 1 , n , arr[i] - 1);
  204. 	}
  205. 	scanf("%d" , &q);
  206. 	while(q--){
  207. 		scanf("%d %d" , &x , &y);
  208. 		inv -= x - 1 - trie.get(1 , x - 1 , arr[x]);
  209. 		inv -= trie.get(x + 1 , n , arr[x] - 1);
  210. 		trie.update(x , y);
  211. 		inv += x - 1 - trie.get(1 , x - 1 , arr[x]);
  212. 		inv += trie.get(x + 1 , n , arr[x] - 1);
  213. 		printf("%lld\n" , inv);
  214. 	}
  215. }
Success #stdin #stdout 0.03s 50192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oQZBU7
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!