Advertisement
Josif_tepe

Untitled

Feb 27th, 2023
617
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <stack>
  8. #include <queue>
  9.  
  10. using namespace std;
  11. const int maxn = 1e5 + 10;
  12. const int INF = 2e9;
  13. struct node {
  14.     int a, b;
  15.     node () {}
  16.     node(int _a, int _b) {
  17.         a = _a;
  18.         b = _b;
  19.     }
  20. };
  21. void merge_node(node & tree_node, node & L, node & R) {
  22.     vector<int> v{L.a, L.b, R.a, R.b};
  23.     sort(v.begin(), v.end());
  24.     tree_node = node(v[2], v[3]);
  25. }
  26. node merge_query(node L, node R) {
  27.     vector<int> v{L.a, L.b, R.a, R.b};
  28.     sort(v.begin(), v.end());
  29.     return node(v[2], v[3]);
  30. }
  31. int arr[maxn];
  32. node segment_tree[3 * maxn];
  33.  
  34. void build_tree(int L, int R, int position) {
  35.     if(L == R) {
  36.         segment_tree[position] = node(arr[L], -INF);
  37.     }
  38.     else {
  39.         int middle = (L + R) / 2;
  40.         build_tree(L, middle, 2 * position);
  41.         build_tree(middle + 1, R, 2 * position + 1);
  42.         merge_node(segment_tree[position], segment_tree[2 * position], segment_tree[2 * position + 1]);
  43.     }
  44. }
  45. // L R i L R j L R
  46. node query(int L, int R, int position, int i, int j) {
  47.     if(i <= L and R <= j) {
  48.         return segment_tree[position];
  49.     }
  50.     if(R < i or j < L) {
  51.         return node(-INF, -INF);
  52.     }
  53.     int middle = (L + R) / 2;
  54.     return merge_query(query(L, middle, 2 * position, i, j), query(middle + 1, R, 2 * position + 1, i, j));
  55. }
  56. void update(int L, int R, int position, int idx, node new_value) {
  57.     if(L == R) {
  58.         segment_tree[position] = new_value;
  59.         return;
  60.     }
  61.     int middle = (L + R) / 2;
  62.     if(idx <= middle) {
  63.         update(L, middle, 2 * position, idx, new_value);
  64.     }
  65.     else {
  66.         update(middle + 1, R, 2 * position + 1, idx, new_value);
  67.     }
  68.     merge_node(segment_tree[position], segment_tree[2 * position], segment_tree[2 * position + 1]);
  69. }
  70. int main() {
  71.     ios_base::sync_with_stdio(false);
  72.     int n;
  73.     cin >> n;
  74.    
  75.     for(int i = 0; i < n; i++) {
  76.         cin >> arr[i];
  77.     }
  78.     build_tree(0, n - 1, 1);
  79.    
  80.     int q;
  81.     cin >> q;
  82.    
  83.     for(int i = 0; i < q; i++) {
  84.         char c;
  85.         cin >> c;
  86.        
  87.         if(c == 'U') {
  88.             int idx, new_value;
  89.             cin >> idx >> new_value;
  90.             idx--;
  91.             update(0, n - 1, 1, idx, node(new_value, -INF));
  92.         }
  93.         else {
  94.             int a, b;
  95.             cin >> a >> b;
  96.             a--; b--;
  97.            
  98.             node tmp = query(0, n - 1, 1, a, b);
  99.             cout << tmp.a + tmp.b << endl;
  100.            
  101.         }
  102.     }
  103.    
  104.     return 0;
  105. }
  106.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement