fork download
copy 
  1. /************************************
  2.  *	AUTHOR: 		Divyansh Gaba	*
  3.  *	INSTITUTION: 	ASET, BIJWASAN	*
  4.  ************************************/
  5. #include<bits/stdc++.h>
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0);
  7. #define F first
  8. #define S second
  9. #define PB push_back
  10. #define MP make_pair
  11. #define REP(i,a,b) for (int i = a; i <= b; i++)
  12.  
  13.  
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17. typedef vector<int> vi;
  18. typedef pair<int,int> pi;
  19. const int N = 1e5;
  20. const int INF = 0x3f3f3f3f;
  21. const int MAXN = 1e9 +7;
  22. int n;
  23. int seg[2*N];
  24. void build()
  25. {
  26.  
  27.     for(int i = n-1;i>0;i--) seg[i] =min(seg[i<<1],seg[i<<1|1]);
  28. }
  29. int query(int l,int r)
  30. {
  31.     int res = MAXN;
  32.     for(l+=n,r+=n;l<r;l>>=1,r>>=1)
  33.     {
  34.         if(l&1)
  35.             res = min(res,seg[l++]);
  36.         if(r&1)
  37.             res = min(res,seg[--r]);
  38.     }
  39.     return res;
  40. }
  41. void update(int p,int val)
  42. {
  43.     for (seg[p += n] = val; p > 1; p >>= 1) seg[p>>1] = min(seg[p] , seg[p^1]);
  44. }
  45. int main()
  46. {
  47. 	fast;
  48. 	int q;
  49. 	cin>>n>>q;
  50. 	memset(seg,INF,sizeof(seg));
  51. 	for(int i =0;i<n;i++)
  52.         cin>>seg[i+n];
  53.     build();
  54.     while(q--)
  55.     {
  56.         char c;
  57.         cin>>c;
  58.         if(c == 'q')
  59.         {
  60.             int l,r;
  61.             cin>>l>>r;
  62.             cout<<query(l-1,r)<<endl;
  63.         }
  64.         else
  65.         {
  66.             int p,val;
  67.             cin>>p>>val;
  68.             update(p-1,val);
  69.         }
  70.     }
  71. 	return 0;
  72.  
  73. }
  74.  
Success #stdin #stdout 0s 16024KB
comments (?)
stdin
copy 
6 5

1 5 2 4 3 0

q 1 5

u 5 -1

q 1 5

q 1 4

q 1 3
stdout
copy 
1
-1
1
1
https://ideone.com/5jPjvT
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!