fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 200005;
  4. int n, q, segTree[4 * maxn];
  5.  
  6. inline char readChar() {
  7. 	const int S = 1<<20; // buffer size
  8. 	static char buf[S], *p = buf, *q = buf;
  9. 	if(p == q && (q = (p=buf)+fread(buf,1,S,stdin)) == buf) return EOF;
  10. 	return *p++;
  11. }
  12.  
  13. inline int readInt() {
  14. 	int x = 0, c = readChar(), neg = false;
  15. 	while(('0' > c || c > '9') && c!='-' && c!=EOF) c = readChar();
  16. 	if(c == '-') neg = true, c = readChar();
  17. 	while('0' <= c && c <= '9') x = x*10 + (c^'0'), c = readChar();
  18. 	if(neg) x = -x;
  19. 	return x; // returns 0 if EOF
  20. }
  21.  
  22. void update(int ux, int u, int x, int l, int r){
  23.     if (l == r){
  24.         segTree[x] = u;
  25.         return;
  26.     }
  27.     int mid = (l + r) >> 1;
  28.     if (ux <= mid) update(ux, u, 2 * x, l, mid);
  29.     else update(ux, u, 2 * x + 1, mid + 1, r);
  30.     segTree[x] = min(segTree[2 * x], segTree[2 * x + 1]);
  31. }
  32.  
  33. int query(int ql, int qr, int x, int l, int r){
  34.     if (ql <= l && r <= qr) return segTree[x];
  35.     int mid = (l + r) >> 1, ret = 1e9;
  36.     if (ql <= mid) ret = query(ql, qr, 2 * x, l, mid);
  37.     if (mid < qr) ret = query(ql, qr, 2 * x + 1, mid + 1, r);
  38.     return ret;
  39. }
  40.  
  41. int main(){
  42.     n = readInt();
  43.     q = readInt();
  44.     for (int i = 1, a; i <= n; i++){
  45.         a = readInt();
  46.         update(i, a, 1, 1, n);
  47.     }
  48.     for (int i = 0, type, a, b; i < q; i++){
  49.         type = readInt();
  50.         a = readInt();
  51. 		b = readInt();
  52.         if (type == 1){
  53.             update(a, b, 1, 1, n);
  54.         }
  55.         else{
  56.             cout << query(a, b, 1, 1, n) << "\n";
  57.         }
  58.     }
  59. }
Success #stdin #stdout 0.01s 5632KB
comments (?)
stdin
copy 
8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 2 3
2 1 4
stdout
copy 
2
1
3
https://ideone.com/h7rtIB
language:
C++14 (gcc 8.3)
created:
2 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!