fork download
copy 
  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 = 2e5 + 5; 
  11.  
  12. int n, q; 
  13. int p[N], a[2][N]; 
  14.  
  15. int seg[2][4 * N]; 
  16.  
  17. void build(int i, int id, int l, int r) {
  18. 	if (l == r) {
  19. 		seg[i][id] = a[i][l];  
  20. 		return;  
  21. 	}
  22. 	int mid = (l + r) >> 1;  
  23. 	build(i, id << 1, l, mid); 
  24. 	build(i, id << 1 | 1, mid + 1, r); 
  25. 	seg[i][id] = min(seg[i][id << 1], seg[i][id << 1 | 1]); 
  26. }
  27.  
  28. void update(int i, int id, int l, int r, int pos, int val) {
  29. 	if (l > pos || r < pos) return; 
  30.  
  31. 	if (l == r) {
  32. 		seg[i][id] = val; 
  33. 		return; 
  34. 	}
  35.  
  36. 	int mid = (l + r) >> 1; 
  37. 	update(i, id << 1, l, mid, pos, val); 
  38. 	update(i, id << 1 | 1, mid + 1, r, pos, val); 
  39.  
  40. 	seg[i][id] = min(seg[i][id << 1], seg[i][id << 1 | 1]); 
  41. }
  42.  
  43. int getMin(int i, int id, int l, int r, int u, int v) {
  44. 	if (l > v || r < u) return INF;  
  45.  
  46. 	if (u <= l && r <= v) return seg[i][id]; 
  47.  
  48. 	int mid = (l + r) >> 1; 
  49. 	return min(getMin(i, id << 1, l, mid, u, v), getMin(i, id << 1 | 1, mid + 1, r, u, v)); 
  50. }
  51.  
  52. int main() {
  53. 	ios::sync_with_stdio(0); cin.tie(0);  	
  54. 	cin >> n >> q; 
  55. 	for (int i = 1; i <= n; i++) {
  56. 		cin >> p[i];  
  57. 		a[0][i] = p[i] + i;  
  58. 		a[1][i] = p[i] - i; 
  59. 	} 
  60.  
  61. 	build(0, 1, 1, n);  
  62. 	build(1, 1, 1, n); 
  63.  
  64. 	while (q--) {
  65. 		int type; cin >> type; 
  66.  
  67. 		if (type == 1) {
  68. 			int k, val; 
  69. 			cin >> k >> val; 
  70. 			update(0, 1, 1, n, k, val + k); 
  71. 			update(1, 1, 1, n, k, val - k);  
  72. 			p[k] = val; 
  73. 		}
  74. 		else {
  75. 			int k; cin >> k;   
  76. 			// Xét các chung cư có vị trí >= k
  77. 			int ans = -k + getMin(0, 1, 1, n, k, n);  
  78. 			// Xét các chung cư có vị trí < k
  79. 			if (k - 1 >= 1) ans = min(ans, k + getMin(1, 1, 1, n, 1, k - 1)); 
  80.  
  81. 			cout << ans << '\n'; 
  82. 		}
  83. 	}
  84. }
Success #stdin #stdout 0s 7764KB
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/J92VF8
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!