fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int tree[1 << 21];
  5. int M = 1;
  6.  
  7. void ne(int v, int val) {
  8.     v += M;
  9.     tree[v] = val;
  10.     v /= 2;
  11.     while (v > 0) {
  12.         tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  13.         v /= 2;
  14.     }
  15. }
  16.  
  17. int dp(int a, int b) {
  18.     a += M;
  19.     b += M;
  20.     int res = max(tree[a], tree[b]);
  21.     while (a / 2 != b / 2) {
  22.         if (a % 2 == 0) res = max(res, tree[a + 1]);
  23.         if (b % 2 == 1) res = max(res, tree[b - 1]);
  24.         a /= 2;
  25.         b /= 2;
  26.     }
  27.     return res;
  28. }
  29.  
  30. int main() {
  31.     ios_base::sync_with_stdio(0);
  32.     cin.tie(0);
  33.  
  34.     int n, m;
  35.     cin>>n>>m;
  36.  
  37.     while (M <= n) M *= 2;
  38.  
  39.     for (int i = 1; i <= n; i++) {
  40.         cin >> tree[M + i];
  41.     }
  42.  
  43.     for (int i = M - 1; i >= 1; i--) {
  44.         tree[i] = max(tree[2 * i], tree[2 * i + 1]);
  45.     }
  46.  
  47.     while (m--) {
  48.         int tajp, x, y;
  49.         cin >> tajp >> x >> y;
  50.         if (tajp == 1) {
  51.             ne(x, y);
  52.         } else {
  53.             cout << dp(x, y) << "\n";
  54.         }
  55.     }
  56. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
5 6
3 6 2 0 1
1 3 8
2 2 4
1 4 6
1 2 0
1 3 4
2 3 5
stdout
copy 
8
6
https://ideone.com/d1uBN3
language:
C++14 (gcc 8.3)
created:
2 hours 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!