# Untitled

Aug 20th, 2019
64
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //http://bkdnoj.dut.udn.vn/public/practice_problem.php?id=IT1
2. #include<bits/stdc++.h>
3. using namespace std;
4. #define FOR(i,a,b) for(int i=a;i<=b;++i)
5. #define FOD(i,a,b) for(int i=a;i>=b;--i)
6. #define FRSZ(i, a) for(int i = 0 ; i < a.size() ; ++i)
7. #define FDSZ(i, a) for(int i = a.size() - 1 ; i >= 0 ; --i)
8.
9. #define debug(x) cout << #x << " = " << x << endl;
10. #define debugvi(x) {FRSZ(_, x) cout << x[_] << " "; cout << endl;}
11. #define debugarr(x, n) {FOR(_, 1, n) cout << x[_] << " "; cout << endl;}
12.
13. #define fi first
14. #define se second
15. #define pb push_back
16.
17. #define ll long long
18. #define ull long long
19. typedef pair<int, int> ii;
20. const int MAX = 4*100000;
21. const int INF = 0x3f3f3f3f;
22. ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
23. ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
24. ll power(ll a, ll b, ll ret = 1LL) {
25. while (b--) ret = (ret * a);
26. return ret;
27. }
28. ll sqr(int a){return (ll)(a*a);}
29.
30. int st[MAX], arr[MAX], n, q;
31.
32. void build(int id, int l, int r)
33. {
34. if (l==r)
35. {
36. st[id]=arr[l];
37. return;
38. }
39. int mid=(l+r)/2;
40. build(2*id,l,mid);
41. build(2*id+1,mid+1,r);
42. st[id] = min(st[2*id],st[2*id+1]);
43. }
44.
45. int get(int id, int l, int r, int s, int e)
46. {
47. if (s<=l && e>=r) return st[id];
48. else if (e<l || s>r) return INT_MAX;
49. else
50. {
51. int mid=(l+r)/2;
52. return min(get(2*id,l,mid,s,e),get(2*id+1,mid+1,r,s,e));
53. }
54. }
55.
56. void update(int id, int s, int e, int index, int val)
57. {
58. if (s==e)
59. {
60. arr[index]=val;
61. st[id]=min(st[id],val);
62. }
63. else
64. {
65. int mid=(s+e)/2;
66. if (s<=index && index<=mid) update(id*2,s,mid,index,val);
67. else update(2*id+1,mid+1,e,index,val);
68. st[id]=min(st[2*id],st[2*id+1]);
69.
70. }
71. }
72. int main()
73. {
74. ios::sync_with_stdio(false);
75. cin.tie(NULL);cout.tie(NULL);
76.
77. freopen("data.inp","r",stdin);
78. freopen("data.out","w",stdout);
79.
80. memset(st,INT_MAX,sizeof(st));
81. cin>>n>>q;
82. FOR(i,1,n) cin>>arr[i];
83. build(1,1,n);
84. while(q--)
85. {
86. char type;cin>>type;
87. if (type=='u')
88. {
89. int index, val;cin>>index>>val;
90. update(1,1,n,index,val);
91. }
92. else
93. if (type=='q')
94. {
95. int left, right;
96. cin>>left>>right;
97. cout<<get(1,1,n,left,right)<<"\n";
98. }
99. }
100.
101. return 0;
102. }
RAW Paste Data