SHARE
TWEET

Untitled

Lamisk Aug 20th, 2019 61 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top