SHARE
TWEET

Untitled

a guest Aug 26th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <math.h>
  4. #include <vector>
  5. #include <set>
  6. #include <unordered_set>
  7. #include <tuple>
  8. #include <map>
  9. #include <unordered_map>
  10. #include <string>
  11. #include <string.h>
  12. #include <utility>
  13. #include <algorithm>
  14. #include <queue>
  15. #include <deque>
  16. #include <iterator>
  17. #include <stdlib.h>
  18. #include <cstdlib>
  19. #include <bitset>
  20. #include <fstream>
  21.  
  22. using namespace std;
  23.  
  24. struct TREE {
  25.     vector<int> tree;
  26.  
  27.     TREE(vector<int>& mas) {
  28.         int a = mas.size();
  29.         tree.resize(a << 2);
  30.     }
  31.  
  32.     void build(int v, int l, int r, vector<int>& mas) {
  33.         if (r - l == 1) {
  34.             tree[v] = l;
  35.             return;
  36.         }
  37.         int m = (r + l) >> 1;
  38.         build((v << 1) + 1, l, m, mas);
  39.         build((v << 1) + 2, m, r, mas);
  40.         tree[v] = (mas[tree[(v << 1) + 1]] >= mas[tree[(v << 1) + 2]] ? tree[(v << 1) + 1] : tree[(v << 1) + 2]);
  41.     }
  42.  
  43.     int get_ans(int v, int l, int r, int askl, int askr, vector<int>& mas) {
  44.         if (l >= askr || r <= askl) {
  45.             return mas.size() - 1;
  46.         }
  47.         if (l >= askl && r <= askr) {
  48.             return tree[v];
  49.         }
  50.         int m = (l + r) >> 1;
  51.         int ans1 = get_ans((v << 1) + 1, l, m, askl, askr, mas);
  52.         int ans2 = get_ans((v << 1) + 2, m, r, askl, askr, mas);
  53.         return (mas[ans1] >= mas[ans2] ? ans1 : ans2);
  54.     }
  55.  
  56.     void change(int v, int l, int r, int pos, int value, vector<int>& mas) {
  57.         if (r - l == 1) {
  58.             mas[l] = value;
  59.             return;
  60.         }
  61.         int m = ((r + l) >> 1);
  62.         if (pos < m) {
  63.             change((v << 1) + 1, l, m, pos, value, mas);
  64.         } else {
  65.             change((v << 1) + 2, m, r, pos, value, mas);
  66.         }
  67.         tree[v] = (mas[tree[(v << 1) + 1]] >= mas[tree[(v << 1) + 2]] ? tree[(v << 1) + 1] : tree[(v << 1) + 2]);
  68.     }
  69. };
  70.  
  71. int main() {
  72.     int n = 0; cin >> n;
  73.     vector<int> mas(n);
  74.     for (int i = 0; i < n; ++i) {
  75.         cin >> mas[i];
  76.     }
  77.     TREE tree (mas);
  78.     tree.build(0, 0, n, mas);
  79.     mas.push_back(INT32_MIN);
  80.     int k = 0; cin >> k;
  81.     for (int i = 0; i < k; ++i) {
  82.         char t;
  83.         int x, y;
  84.         cin >> t >> x >> y;
  85.         if (t == 's') {
  86.             cout << tree.get_ans(0, 0, n, x - 1, y, mas) + 1 << " ";
  87.         } else if (t == 'u') {
  88.             tree.change(0, 0, n, x - 1, y, mas);
  89.         }
  90.     }
  91. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top