fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <algorithm>
  6. #include <set>
  7. #include <vector>
  8. #include <map>
  9. #include <queue>
  10. #include <stack>
  11.  
  12. using namespace std;
  13.  
  14. #define forn(i, n) for(int i = 0; i < int(n); i++)
  15. #define forv(i, v) for(int i = 0; i < int(v.size()); i++)
  16.  
  17. #define mp make_pair
  18. #define pb push_back
  19. #define all(x) x.begin(), x.end()
  20.  
  21.  
  22. typedef long long ll;
  23. typedef long double ld;
  24.  
  25. inline int ni() { int a; scanf("%d", &a); return a; }
  26.  
  27. const int max_n = 100000;
  28.  
  29. struct treap {
  30. 	int l, r, key, value, size, count;
  31.  
  32. 	treap() { }
  33. 	treap(int key, int value) { this->l = this->r = -1, this->key = key, this->value = value, this->size = 1, this->count = 1; }
  34. };
  35.  
  36. treap treaps[60 * max_n];
  37. int arr[max_n], st[4 * max_n];
  38. char buffer[8];
  39.  
  40. int treaps_sz = 0;
  41.  
  42. inline int rand_int() {
  43. 	return rand() << 15 + rand();
  44. }
  45.  
  46. inline int treap_size(int t) {
  47. 	if(t == -1) return 0;
  48. 	return treaps[t].size;
  49. }
  50.  
  51. inline int treap_create(int value) {
  52. 	treaps[treaps_sz] = treap(rand_int(), value);
  53. 	return treaps_sz++;
  54. }
  55.  
  56. inline void treap_recalc(int t) {
  57. 	treaps[t].size = treap_size(treaps[t].l) + treap_size(treaps[t].r) + treaps[t].count;
  58. } 
  59.  
  60. int treap_merge(int l, int r) {
  61. 	if(l == -1) return r;
  62. 	if(r == -1) return l;
  63.  
  64. 	if(treaps[l].key > treaps[r].key) {
  65. 		treaps[l].r = treap_merge(treaps[l].r, r);
  66. 		treap_recalc(l);
  67. 		return l;
  68. 	} else {
  69. 		treaps[r].l = treap_merge(l, treaps[r].l);
  70. 		treap_recalc(r);
  71. 		return r;
  72. 	}
  73. }
  74.  
  75. pair < int, int > treap_split(int t, int value) {
  76. 	if(t == -1) return mp(-1, -1);
  77.  
  78. 	if(treaps[t].value >= value) {
  79. 		pair < int, int > s = treap_split(treaps[t].l, value);
  80. 		treaps[t].l = s.second;
  81. 		s.second = t;
  82. 		treap_recalc(t);
  83. 		return s;
  84. 	} else {
  85. 		pair < int, int > s = treap_split(treaps[t].r, value);
  86. 		treaps[t].r = s.first;
  87. 		s.first = t;
  88. 		treap_recalc(t);
  89. 		return s;
  90. 	}
  91. }
  92.  
  93. void treap_add(int & t, int value) {
  94. 	pair < int, int > fs = treap_split(t, value);
  95. 	pair < int, int > ss = treap_split(fs.second, value + 1);
  96.  
  97. 	if(ss.first == -1) {
  98. 		ss.first = treap_create(value);
  99. 	} else {
  100. 		treaps[ss.first].count++;
  101. 		treap_recalc(ss.first);
  102. 	}
  103.  
  104. 	t = treap_merge(fs.first, treap_merge(ss.first, ss.second));
  105. }
  106.  
  107. void treap_remove(int & t, int value) {
  108. 	pair < int, int > fs = treap_split(t, value);
  109. 	pair < int, int > ss = treap_split(fs.second, value + 1);
  110.  
  111. 	if(ss.first != -1) {
  112. 		treaps[ss.first].count--;
  113.  
  114. 		if(treaps[ss.first].count == 0) ss.first = -1;
  115. 	}
  116.  
  117. 	t = treap_merge(fs.first, treap_merge(ss.first, ss.second));
  118. }
  119.  
  120. inline int treap_how_much(int & t, int a, int b) {
  121. 	pair < int, int > fs = treap_split(t, a);
  122. 	pair < int, int > ss = treap_split(fs.second, b + 1);
  123. 	int res = treap_size(ss.first);
  124. 	t = treap_merge(fs.first, treap_merge(ss.first, ss.second));
  125. 	return res;
  126. }
  127.  
  128. inline int left(int v) { return (v << 1); }
  129. inline int right(int v) { return (v << 1) + 1; }
  130.  
  131. void st_build(int v, int l, int r) {
  132. 	st[v] = -1;
  133.  
  134. 	if(l != r) {
  135. 		int m = (l + r) >> 1;
  136. 		st_build(left(v), l, m);
  137. 		st_build(right(v), m + 1, r);
  138. 	}
  139.  
  140. 	for(int i = l; i <= r; i++) treap_add(st[v], arr[i]);
  141. }
  142.  
  143. void st_remove_and_add(int v, int l, int r, int ind, int old_val, int new_val) {
  144. 	if(l != r) {
  145. 		int m = (l +r) >> 1;
  146. 		if(ind <= m) st_remove_and_add(left(v), l, m, ind, old_val, new_val);
  147. 		else st_remove_and_add(right(v), m + 1, r, ind, old_val, new_val);
  148. 	}
  149.  
  150. 	treap_remove(st[v], old_val);
  151. 	treap_add(st[v], new_val);
  152. }
  153.  
  154. int st_query(int v, int l, int r, int tl, int tr, int a, int b) {
  155. 	if(l == tl && r == tr) {
  156. 		return treap_how_much(st[v], a, b);
  157. 	} else {
  158.  
  159. 		int m = (l + r) >> 1, res = 0;
  160.  
  161. 		if(tl <= m) res += st_query(left(v), l, m, tl, min(tr, m), a, b);
  162. 		if(tr > m) res += st_query(right(v), m + 1, r, max(m + 1, tl), tr, a, b);
  163.  
  164. 		return res;
  165. 	}
  166. }
  167.  
  168. int main() {
  169. 	//freopen("h8.in", "r", stdin);
  170. 	//freopen("h8.out", "w", stdout);
  171.  
  172. 	int n = ni(), m = ni();
  173.  
  174. 	forn(i, n) arr[i] = ni();
  175.  
  176. 	st_build(1, 0, n - 1);
  177.  
  178. 	forn(i, m) {
  179. 		scanf("%s", buffer);
  180.  
  181. 		if(buffer[0] == 'G') {
  182. 			int l = ni() - 1, r = ni() - 1, a = ni(), b = ni();
  183. 			printf("%d\n", st_query(1, 0, n - 1, l, r, a, b));
  184. 		} else {
  185. 			int ind = ni() - 1, value = ni();
  186. 			st_remove_and_add(1, 0, n - 1, ind, arr[ind], value);
  187. 		}
  188. 	}
  189.  
  190.  
  191. 	return 0;
  192. }
Success #stdin #stdout 0.01s 145280KB
comments (?)
stdin
copy 
5 1
3 4 1 3 5
GET 3 5 1 2
stdout
copy 
1
https://ideone.com/2WxDs
language:
C++ (gcc 8.3)
created:
12 years 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!