fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 30005;
  5. int Arr[MX];
  6. multiset <int> tree[4 * MX];
  7.  
  8. void build(int node, int st, int en){
  9. 	if(st == en){
  10. 		tree[node].clear();
  11. 		tree[node].insert(Arr[st]);
  12. 		return;
  13. 	}
  14.  
  15. 	int left = 2*node, right = left + 1, mid = (en + st)/2;
  16. 	build(left, st, mid);
  17. 	build(right, mid + 1, en);
  18.  
  19. 	tree[node].clear();
  20. 	tree[node].insert(tree[left].begin(), tree[left].end());
  21. 	tree[node].insert(tree[right].begin(), tree[right].end());
  22. }
  23.  
  24. void update(int node, int st, int en, int l, int r, int newV, int oldV){
  25. 	if(st > r || en < l) return;
  26. 	if(st >= l && en <= r){
  27. 		Arr[st] = newV;
  28. 		tree[node].clear();
  29. 		tree[node].insert(newV);
  30. 		return;
  31. 	}
  32.  
  33. 	int left = 2*node, right = left + 1, mid = (en + st)/2;
  34. 	update(left, st, mid, l, r, newV, oldV);
  35. 	update(right, mid + 1, en, l, r, newV, oldV);
  36. 	multiset<int>:: iterator it;
  37. 	it = tree[node].lower_bound(oldV);
  38. 	tree[node].erase(it);
  39. 	tree[node].insert(newV);
  40. }
  41.  
  42. int query(int node, int st, int en, int l, int r, int num){
  43. 	if(st > r || en < l) return 0;
  44. 	if(st >= l && en <= r){
  45. 		int sz = en - st + 1;
  46. 		multiset<int>:: iterator it;
  47. 	    it = tree[node].upper_bound(num);
  48. 	    int id = distance(tree[node].begin(), it);
  49. 	    return (sz - id);
  50. 	}
  51. 	int left = 2*node, right = left + 1, mid = (en + st)/2;
  52. 	int p = query(left, st, mid, l, r, num);
  53. 	int q = query(right, mid + 1, en, l, r, num);
  54. 	return p + q;
  55. }
  56.  
  57. int main() {
  58. 	int n, q, flag, l, r, num;
  59. 	for(; scanf("%d", &n) == 1 ;){
  60. 		for(int i = 1; i <= n; i++) scanf("%d", &Arr[i]);
  61. 		build(1,1,n);
  62.  
  63. 		scanf("%d", &q);
  64. 		for(int i = 0; i<q; i++){
  65. 			scanf("%d", &flag);
  66. 			if(flag){
  67. 			    scanf("%d %d %d", &l, &r, &num);
  68. 			    printf("%d\n", query(1,1,n,l,r,num));
  69. 			}else{
  70. 				scanf("%d %d", &l, &num);
  71. 				update(1,1,n,l,l,num,Arr[l]);
  72. 			}
  73. 		}
  74. 	}
  75. 	return 0;
  76. }
Success #stdin #stdout 0s 6404KB
comments (?)
stdin
copy 
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2
stdout
copy 
2
1
2
https://ideone.com/gDAmUW
language:
C++14 (gcc 8.3)
created:
8 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!