Advertisement
Josif_tepe

Untitled

Mar 2nd, 2023
651
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 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. #include <fstream>
  10. using namespace std;
  11. typedef int ll;
  12. const int maxn = 1e5 + 10;
  13. const int INF = 2e9;
  14. int arr[maxn];
  15. pair<int, int> segment_tree[3 * maxn];
  16. pair<int, int> merged_nodes(pair<int, int>  A, pair<int, int> B) {
  17.     vector<int> v = {A.first, A.second, B.first, B.second};
  18.     sort(v.begin(), v.end());
  19.     return make_pair(v[2], v[3]);
  20. }
  21. void build_tree(int L, int R, int position) {
  22.     if(L == R) {
  23.         segment_tree[position] = make_pair(arr[L], -INF);
  24.     }
  25.     else {
  26.         int middle = (L + R) / 2;
  27.         build_tree(L, middle, 2 * position);
  28.         build_tree(middle + 1, R,  2 * position + 1);
  29.         segment_tree[position] = merged_nodes(segment_tree[2 * position], segment_tree[2 * position + 1]);
  30.     }
  31. }
  32. // L R i L R j L R
  33. pair<int, int> query(int L, int R, int position, int i, int j) {
  34.     if(i <= L and R <= j) {
  35.         return segment_tree[position];
  36.     }
  37.     if(R < i or j < L) {
  38.         return make_pair(-INF, -INF);
  39.     }
  40.     int middle = (L + R) / 2;
  41.     return merged_nodes(query(L, middle, 2 * position, i, j), query(middle + 1, R, 2 * position + 1, i, j));
  42. }
  43. void update(int L, int R, int position, int idx, int new_value) {
  44.     if(L == R) {
  45.         segment_tree[position] = make_pair(new_value, -INF);
  46.         return;
  47.     }
  48.     int middle = (L + R) / 2;
  49.     if(idx <= middle) {
  50.         update(L, middle, 2 * position, idx, new_value);
  51.     }
  52.     else {
  53.         update(middle + 1, R, 2 * position + 1, idx, new_value);
  54.     }
  55.     segment_tree[position] = merged_nodes(segment_tree[2 * position], segment_tree[2 * position + 1]);
  56. }
  57. int main(){
  58.     ios_base::sync_with_stdio(false);
  59.     int n;
  60.     cin >> n;
  61.     for(int i = 0; i < n; i++) {
  62.         cin >> arr[i];
  63.     }
  64.     build_tree(0, n - 1, 1);
  65.     int q;
  66.     cin >> q;
  67.    
  68.     for(int i= 0; i < q; i++) {
  69.         char c;
  70.         cin >> c;
  71.         if(c == 'U') {
  72.             int idx, new_value;
  73.             cin >> idx >> new_value;
  74.             idx--;
  75.            
  76.             update(0, n - 1, 1, idx, new_value);
  77.         }
  78.         else {
  79.             int a, b;
  80.             cin >> a >> b;
  81.             a--; b--;
  82.            
  83.             pair<int, int> p = query(0, n - 1, 1, a, b);
  84.             cout << p.first + p.second << endl;
  85.         }
  86.     }
  87.     return 0;
  88. }
  89.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement