fork 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 LN = 15;
  18. int n;
  19. struct snode{
  20. 	snode* left;
  21. 	snode* right;
  22. 	int cnt;
  23. 	snode(){
  24. 		left = NULL;
  25. 		right = NULL;
  26. 		cnt = 0;
  27. 	}
  28. };
  29. struct segtree{
  30. 	snode* root;
  31. 	segtree(){
  32. 		root = new snode();
  33. 	}
  34. 	int cnt(snode* tree){
  35. 		if(tree){
  36. 			return tree -> cnt;
  37. 		}
  38. 		return 0;
  39. 	}
  40. 	void insert(snode* &tree , int l , int r , int val){
  41. 		if(!tree){
  42. 			tree = new snode();
  43. 		}
  44. 		if(l == r){
  45. 			tree -> cnt = 1;
  46. 		}
  47. 		else{
  48. 			int mid = l + r >> 1;
  49. 			if(mid >= val){
  50. 				insert(tree -> left , l , mid , val);
  51. 			}
  52. 			else{
  53. 				insert(tree -> right , mid + 1 , r , val);
  54. 			}
  55. 			tree -> cnt = cnt(tree -> left) + cnt(tree -> right);
  56. 		}
  57. 	}
  58. 	void erase(snode* &tree , int l , int r , int val){
  59. 		assert(tree);
  60. 		if(l == r){
  61. 			tree -> cnt = 0;
  62. 		}
  63. 		else{
  64. 			int mid = l + r >> 1;
  65. 			if(mid >= val){
  66. 				erase(tree -> left , l , mid , val);
  67. 			}
  68. 			else{
  69. 				erase(tree -> right , mid + 1 , r , val);
  70. 			}
  71. 			tree -> cnt = cnt(tree -> left) + cnt(tree -> right);
  72. 		}
  73. 	}
  74. 	void insert(int key){
  75. 		insert(root , 1 , n , key);
  76. 	}
  77. 	void erase(int key){
  78. 		erase(root , 1 , n , key);
  79. 	}
  80. 	int query(snode* tree , int l , int r , int ql , int qr){
  81. 		if(l > qr || r < ql || !tree){
  82. 			return 0;
  83. 		}
  84. 		if(l >= ql && r <= qr){
  85. 			return cnt(tree);
  86. 		}
  87. 		int mid = l + r >> 1;
  88. 		return query(tree -> left , l , mid , ql , qr) + query(tree -> right , mid + 1 , r , ql , qr);
  89. 	}
  90. 	int range(int l , int r){
  91. 		return query(root , 1 , n , l , r);
  92. 	}
  93. };
  94. int arr[N];
  95. int q;
  96. int x , y;
  97. long long inv = 0;
  98. struct node{
  99.     segtree indices;
  100.     int left;
  101.     int right;
  102.     node(){
  103.         left = -1;
  104.         right = -1;
  105.     }
  106. };
  107. struct TRIE{
  108. 	node nodes[(N + 10001) * LN];
  109.     int cur;
  110.     TRIE(){
  111.         cur = 0;
  112.     }
  113.     void insert(int num ,int index){
  114.     	int nd = 0;
  115.         for(int i = LN ; i >= 0 ; --i){
  116.             bool b = (num >> i) & 1;
  117.             if(b){
  118.                 if(nodes[nd].right == -1){
  119.                     nodes[nd].right = ++cur;
  120.                 }
  121.                 nd = nodes[nd].right;
  122.                 nodes[nd].indices.insert(index);
  123.             }
  124.             else{
  125.                 if(nodes[nd].left == -1){
  126.                     nodes[nd].left = ++cur;
  127.                 }
  128.                 nd = nodes[nd].left;
  129.                 nodes[nd].indices.insert(index);
  130.             }
  131.         }
  132.     }
  133.     void erase(int num , int index){
  134.         int nd = 0;
  135.         for(int i = LN ; i >= 0 ; --i){
  136.             bool b = (num >> i) & 1;
  137.             if(b){
  138.                 nd = nodes[nd].right;
  139.             }
  140.             else{
  141.                 nd = nodes[nd].left;
  142.             }
  143.             nodes[nd].indices.erase(index);
  144.         }
  145.     }
  146.     void update(int index , int value){
  147.     	erase(arr[index] , index);
  148.     	arr[index] = value;
  149.     	insert(arr[index] , index);
  150.     }
  151.     int get(int l , int r , int k){
  152.         ++k;
  153.         int ret = 0;
  154.         int nd = 0;
  155.         for(int i = LN ; i >= 0 && nd >= 0; --i){
  156.             bool b = (k >> i) & 1;
  157.             if(b){
  158.                 int z = 0;
  159.                 if(nodes[nd].left != -1){
  160.                 	z = nodes[nodes[nd].left].indices.range(l , r);
  161.                 }
  162.                 ret += z;
  163.                 nd = nodes[nd].right;
  164.             }
  165.             else{
  166.                 nd = nodes[nd].left;
  167.             }
  168.         }
  169.         return ret;
  170.     }
  171. };
  172. TRIE trie;
  173. int main(){
  174. 	n = scan();
  175. 	for(int i = 1 ; i <= n ; ++i){
  176. 		//arr[i] = rand() % 50000;
  177. 		//++arr[i];
  178. 		arr[i] = scan();
  179. 		trie.insert(arr[i] , i);
  180. 	}
  181. 	for(int i = n ; i >= 1 ; --i){
  182. 		inv += trie.get(i + 1 , n , arr[i] - 1);
  183. 	}
  184. 	q = scan();
  185. 	while(q--){
  186. 		//x = rand() % n;
  187. 		//++x;
  188. 		//y = rand() % 50000;
  189. 		//++y;
  190. 		x = scan() , y = scan();
  191. 		inv -= x - 1 - trie.get(1 , x - 1 , arr[x]);
  192. 		inv -= trie.get(x + 1 , n , arr[x] - 1);
  193. 		trie.update(x , y);
  194. 		inv += x - 1 - trie.get(1 , x - 1 , arr[x]);
  195. 		inv += trie.get(x + 1 , n , arr[x] - 1);
  196. 		printf("%lld\n" , inv);
  197. 	}
  198. }
Time limit exceeded #stdin #stdout 5s 110976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gxoKfr
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!