fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 2e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 1e5 + 5;  
  11.  
  12. int n, q;  
  13. int a[N];  
  14.  
  15. multiset<int> seg[4 * N]; // seg[id] = multiset chứa các phần tử thuộc đoạn [l, r] mà nút id quản lí
  16.  
  17. void build(int id, int l, int r) { // O(nlog^2(n))
  18. 	if (l == r) {
  19. 		seg[id].insert(a[l]); 
  20. 		return; 
  21. 	}
  22. 	int mid = (l + r) >> 1; 
  23. 	build(id * 2, l, mid); 
  24. 	build(id * 2 + 1, mid + 1, r); 
  25. 	seg[id] = seg[id * 2]; 
  26. 	for (int x : seg[id * 2 + 1]) seg[id].insert(x); 
  27. }
  28.  
  29. void update(int id, int l, int r, int pos, int val) { // O(log^2(n))
  30. 	if (l > pos || r < pos) return; 
  31.  
  32. 	seg[id].erase(seg[id].find(a[pos])); 
  33. 	seg[id].insert(val); 
  34.  
  35. 	if (l == r) return;  
  36.  
  37. 	int mid = (l + r) >> 1; 
  38. 	update(id * 2, l, mid, pos, val); 
  39. 	update(id * 2 + 1, mid + 1, r, pos, val); 
  40. }
  41.  
  42. // Tìm số nhỏ nhất >= k trong đoạn [u, v]
  43. int get(int id, int l, int r, int u, int v, int k) { // O(log^2(n))
  44. 	if (l > v || r < u) return INF; 
  45.  
  46. 	if (u <= l && r <= v) {
  47. 		auto it = seg[id].lower_bound(k);   
  48. 		if (it != seg[id].end()) return (*it); 
  49. 		return INF; 
  50. 	}
  51.  
  52. 	int mid = (l + r) >> 1; 
  53. 	return min(get(id * 2, l, mid, u, v, k), get(id * 2 + 1, mid + 1, r, u, v, k)); 
  54. }
  55.  
  56. int main() {
  57. 	ios::sync_with_stdio(0); cin.tie(0);  	
  58. 	cin >> n >> q; 
  59. 	for (int i = 1; i <= n; i++) cin >> a[i];  
  60.  
  61. 	build(1, 1, n);   
  62.  
  63. 	while (q--) {
  64. 		int type; cin >> type;  
  65.  
  66. 		if (type == 1) {
  67. 			int i, v; 
  68. 			cin >> i >> v; 
  69. 			update(1, 1, n, i, v); 
  70. 			a[i] = v; 
  71. 		}
  72. 		else {
  73. 			int l, r, k; 
  74. 			cin >> l >> r >> k;  
  75. 			int ans = get(1, 1, n, l, r, k);  
  76. 			if (ans == INF) ans = -1;  
  77. 			cout << ans << '\n'; 
  78. 		}
  79. 	}
  80. }
  81.  
Success #stdin #stdout 0.01s 22348KB
comments (?)
stdin 
5 4
1 5 3 4 5
2 1 3 2
2 3 5 6
1 2 2
2 1 5 2
stdout 
3
-1
2
https://ideone.com/aAdRhD
language:
C++14 (gcc 8.3)
created:
1 year 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!