Guest User

Untitled

a guest
Aug 26th, 2019
77
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