Lamisk

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