fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 100000 + 5;
  5. const int SIZE = 4 * N;
  6.  
  7. int n;
  8. int q;
  9. int a[N];
  10. pair<int, int> st[SIZE];
  11.  
  12. pair<int, int> f(pair<int, int> a, pair<int, int> b){
  13. 	if(a.first == b.first) return make_pair(a.first, a.second + b.second);
  14. 	return a < b ? a : b;
  15. }
  16.  
  17. void build(int pos = 1, int l = 0, int r = n - 1){
  18. 	if(l == r){
  19. 		st[pos] = make_pair(a[l], 1);
  20. 		return;
  21. 	}
  22. 	int mi = (l + r) / 2;
  23. 	build(2 * pos, l, mi);
  24. 	build(2 * pos + 1, mi + 1, r);
  25. 	st[pos] = f(st[2 * pos], st[2 * pos + 1]);
  26. }
  27.  
  28. void update(int x, int y, int pos = 1, int l = 0, int r = n - 1){
  29. 	if(l == r){
  30. 		st[pos].first = y;
  31. 		return;
  32. 	}
  33. 	int mi = (l + r) / 2;
  34. 	if(x <= mi) update(x, y, 2 * pos, l, mi);
  35. 	else update(x, y, 2 * pos + 1, mi + 1, r);
  36. 	st[pos] = f(st[2 * pos], st[2 * pos + 1]);
  37. }
  38.  
  39. pair<int, int> query(int x, int y, int pos = 1, int l = 0, int r = n - 1){
  40. 	if(y < l or r < x) return make_pair(INT_MAX, 0); // No hay posiciones que quiera sumar en este rango
  41. 	if(x <= l and r <= y) return st[pos]; // Todo el rango [l, r] está dentro de [x, y]
  42. 	int mi = (l + r) / 2;
  43. 	return f(query(x, y, 2 * pos, l, mi), query(x, y, 2 * pos + 1, mi + 1, r));
  44. }
  45.  
  46. int main() {
  47. 	scanf("%d %d", &n, &q);
  48. 	for(int i = 0; i < n; i++){
  49. 		scanf("%d", a + i);
  50. 	}
  51. 	build();
  52. 	while(q--){
  53. 		int op, l, r;
  54. 		scanf("%d %d %d", &op, &l, &r);
  55. 		if(op == 1) update(l, r);
  56. 		else{
  57. 			pair<int, int> res = query(l, r - 1);
  58. 			printf("%d %d\n", res.first, res.second);
  59. 		}
  60. 	}
  61. 	return 0;
  62. }
Success #stdin #stdout 0.01s 5400KB
comments (?)
stdin
copy 
5 5
3 4 3 5 2
2 0 3
1 1 2
2 0 3
1 0 2
2 0 5
stdout
copy 
3 2
2 1
2 3
https://ideone.com/dm4Phr
language:
C++14 (gcc 8.3)
created:
1 year 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!