Advertisement
KShah

Untitled

Nov 21st, 2021
987
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. int next_2_degree(int value) {
  5.     int i = 0;
  6.     while(value >> i) ++i;
  7.  
  8.     return 1 << i;
  9. }
  10.  
  11. class SegmentTree {
  12. public:
  13.     SegmentTree(const std::vector<std::pair<int, int> >& arr, int n, int defaultValue);
  14.     void Update(int pos, int val);
  15.     int ClosestBigger(int pos, int x);
  16.  
  17. private:
  18.     std::vector<std::pair<int, int> > tree;
  19.     int default_, size_;
  20.    
  21.     int closestBigger(int index, int tleft, int tright, int left, int right, int x);
  22.     void build(int index, int left, int right);
  23.     void update(int index, int left, int right, int pos);
  24. };
  25.  
  26. SegmentTree::SegmentTree(const std::vector<std::pair<int, int> >& arr, int n, int defaultValue)
  27.     : default_(defaultValue), size_(next_2_degree(n) * 2), tree(next_2_degree(n) * 2, {defaultValue, defaultValue}) {
  28.  
  29.     std::copy(arr.begin(), arr.end(), tree.begin() + tree.size() / 2 - 1);
  30.     build(0, 0, size_ / 2 - 1);
  31. }
  32.  
  33. void SegmentTree::build(int index, int left, int right) {
  34.     if (left == right) return;
  35.  
  36.     const int mid = (left + right) / 2;
  37.     build(2 * index + 1, left, mid);
  38.     build(2 * index + 2, mid + 1, right);
  39.     tree[index].first = std::min(tree[2 * index + 1].first, tree[2 * index + 2].first);
  40.     tree[index].second = std::max(tree[2 * index + 1].second, tree[2 * index + 2].second);
  41. }
  42.  
  43.  
  44. int SegmentTree::ClosestBigger(int pos, int x) {
  45.     return closestBigger(0, 0, size_ / 2 - 1, pos - 1, size_ / 2 - 1, x);
  46. }
  47.  
  48. int SegmentTree::closestBigger(int index, int tleft, int tright, int left, int right, int x) {
  49.     if (tleft > right || tright < left) return -2;
  50.    
  51.     if (tleft == tright) {
  52.         if (tree[index].second >= x) {
  53.             return tleft;
  54.         }
  55.         return -2;
  56.     }
  57.    
  58.     const int mid = (tleft + tright) >> 1;
  59.     if (tleft >= left && tright <= right) {
  60.         if (tree[index].second < x) {
  61.             return -2;
  62.         }
  63.         if (tree[index].first >= x) {
  64.             return tleft;
  65.         }
  66.         if (tree[2 * index + 1].second >= x) {
  67.             return closestBigger(2 * index + 1, tleft, mid, left, right, x);
  68.         }
  69.         if (tree[2 * index + 2].second >= x) {
  70.             return closestBigger(2 * index + 2, mid + 1, tright, left, right, x);
  71.         }
  72.         return -2;
  73.     }
  74.     int lans = closestBigger(2 * index + 1, tleft, mid, left, right, x),
  75.         rans = closestBigger(2 * index + 2, mid + 1, tright, left, right, x);
  76.     if (lans != -2) {
  77.         return lans;
  78.     }
  79.     return rans;
  80. }
  81.  
  82. void SegmentTree::Update(int pos, int val) {
  83.     tree[size_ / 2 + pos - 2] = std::make_pair(val, val);
  84.     update(0, 0, size_ / 2 - 1, pos - 1);
  85. }
  86.  
  87. void SegmentTree::update(int index, int left, int right, int pos) {
  88.     if (left == right) return;
  89.  
  90.     const int mid = (left + right) / 2;
  91.     if (pos <= mid) {
  92.         update(2 * index + 1, left, mid, pos);
  93.     } else {
  94.         update(2 * index + 2, mid + 1, right, pos);
  95.     }
  96.     tree[index].first = std::min(tree[2 * index + 1].first, tree[2 * index + 2].first);
  97.     tree[index].second = std::max(tree[2 * index + 1].second, tree[2 * index + 2].second);
  98. }
  99.  
  100. int main() {
  101.     std::ios_base::sync_with_stdio(false);
  102.     std::cin.tie(nullptr);
  103.     std::cout.tie(nullptr);
  104.    
  105.     int n, m;
  106.     std::cin >> n >> m;
  107.    
  108.     std::vector <std::pair<int, int> > arr(n);
  109.     for (int i = 0; i < n; ++i) {
  110.         std::cin >> arr[i].first;
  111.         arr[i].second = arr[i].first;
  112.     }
  113.    
  114.     SegmentTree tree(arr, n, -2);
  115.     for (int i = 0; i < m; ++i) {
  116.         int req, pos, x;
  117.         std::cin >> req >> pos >> x;
  118.         if (req) {
  119.             std::cout << tree.ClosestBigger(pos, x) + 1 << '\n';
  120.         } else {
  121.             tree.Update(pos, x);
  122.         }
  123.     }
  124.  
  125.     return 0;
  126. }
  127.  
  128.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement