fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 2e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12.  
  13. int n, q; 
  14. int p[N], a[2][N]; 
  15.  
  16. struct SegTree {
  17. 	int n;  
  18. 	vector<int> seg; 
  19.  
  20. 	SegTree() {}
  21.  
  22. 	SegTree(int n) : n(n) {
  23. 		seg.resize(4 * n, 0); 
  24. 	}
  25.  
  26. 	void build(int a[], int id, int l, int r) {
  27. 		if (l == r) {
  28. 			seg[id] = a[l];  
  29. 			return;  
  30. 		}
  31. 		int mid = (l + r) >> 1;  
  32. 		build(a, id * 2, l, mid); 
  33. 		build(a, id * 2 + 1, mid + 1, r); 
  34. 		seg[id] = min(seg[id * 2], seg[id * 2 + 1]); 
  35. 	}
  36.  
  37. 	void update(int id, int l, int r, int pos, int val) {
  38. 		if (l > pos || r < pos) return; 
  39. 		if (l == r) {
  40. 			seg[id] = val; 
  41. 			return; 
  42. 		}
  43. 		int mid = (l + r) >> 1; 
  44. 		update(id * 2, l, mid, pos, val); 
  45. 		update(id * 2 + 1, mid + 1, r, pos, val); 
  46. 		seg[id] = min(seg[id * 2], seg[id * 2 + 1]); 
  47. 	}
  48.  
  49. 	int getMin(int id, int l, int r, int u, int v) {
  50. 		if (l > v || r < u) return INF;  
  51. 		if (u <= l && r <= v) return seg[id]; 
  52. 		int mid = (l + r) >> 1; 
  53. 		return min(getMin(id * 2, l, mid, u, v), getMin(id * 2 + 1, mid + 1, r, u, v)); 
  54. 	}
  55. }; 
  56.  
  57. SegTree segtree[2]; 
  58.  
  59. int main() {
  60. 	ios::sync_with_stdio(false); 
  61. 	cin.tie(nullptr);  	
  62. 	cin >> n >> q; 
  63. 	for (int i = 1; i <= n; i++) {
  64. 		cin >> p[i];  
  65. 		a[0][i] = p[i] + i;  
  66. 		a[1][i] = p[i] - i; 
  67. 	} 
  68.  
  69. 	for (int i = 0; i <= 1; i++) {
  70. 		segtree[i] = SegTree(n + 1); 
  71. 		segtree[i].build(a[i], 1, 1, n); 
  72. 	}
  73.  
  74. 	while (q--) {
  75. 		int type; cin >> type; 
  76.  
  77. 		if (type == 1) {
  78. 			int k, val; 
  79. 			cin >> k >> val; 
  80. 			segtree[0].update(1, 1, n, k, val + k); 
  81. 			segtree[1].update(1, 1, n, k, val - k);  
  82. 			p[k] = val; 
  83. 		}
  84. 		else {
  85. 			int k; cin >> k;   
  86. 			// Xét các chung cư có vị trí >= k
  87. 			int ans = -k + segtree[0].getMin(1, 1, n, k, n);  
  88. 			// Xét các chung cư có vị trí < k
  89. 			if (k - 1 >= 1) ans = min(ans, k + segtree[1].getMin(1, 1, n, 1, k - 1)); 
  90. 			cout << ans << '\n'; 
  91. 		}
  92. 	}
  93. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6 3
8 6 4 5 7 5
2 2
1 5 1
2 2
stdout
copy 
5
4
https://ideone.com/j4aoxk
language:
C++14 (gcc 8.3)
created:
39 days 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!