Submission #50856104

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

template <typename Info>
struct SegmentTree {
  struct Node : public Info {
    int l, r, ts;
    Node *lch, *rch;
    Node(int l_ = 0, int r_ = 0, int ts_ = 0)
        : l(l_), r(r_), ts(ts_), lch(nullptr), rch(nullptr) {}
    Node(Node* x, int ts_ = 0) {
      *this = *x;
      this->ts = ts_;
    }
  };

  int l_range, r_range;
  Node* root;
  bool persist;
  int ts;
  SegmentTree(int l, int r, bool persist_ = false)
      : l_range(l), r_range(r), root(nullptr), persist(persist_), ts(0) {
    assert(l_range <= r_range);
  }

  void PushDown(Node* x) {
    if (x->NeedPushDown()) {
      if (persist) {
        if (x->lch && x->lch->ts != ts) x->lch = new Node(x->lch, ts);
        if (x->rch && x->rch->ts != ts) x->rch = new Node(x->rch, ts);
      }
      x->PushDown();
    }
  }

  template <typename F>
  Node* Modify(int from, int to, F f) {
    assert(l_range <= from && from <= to && to <= r_range);
    std::function<Node*(Node*, int, int)> Modify = [&](Node* x, int l, int r) {
      if (!x) {
        x = new Node(l, r, ts);
      } else if (persist && x->ts != ts) {
        x = new Node(x, ts);
      }
      if (from <= x->l && x->r <= to) {
        f(x);
        return x;
      }
      PushDown(x);
      int m = l + (r - l) / 2;
      if (from <= m) x->lch = Modify(x->lch, l, m);
      if (to > m) x->rch = Modify(x->rch, m + 1, r);
      x->Update();
      return x;
    };
    root = Modify(root, l_range, r_range);
    return root;
  }

  template <typename F>
  Node* ModifyPath(int p, F f) {
    assert(l_range <= p && p <= r_range);
    std::function<Node*(Node*, int, int)> Dfs = [&](Node* x, int l, int r) {
      if (!x) {
        x = new Node(l, r, ts);
      } else if (persist && x->ts != ts) {
        x = new Node(x, ts);
      }
      f(x);
      if (x->l == x->r) return x;
      PushDown(x);
      int m = l + (r - l) / 2;
      if (p <= m) x->lch = Dfs(x->lch, l, m);
      else x->rch = Dfs(x->rch, m + 1, r);
      x->Update();
      return x;
    };
    root = Dfs(root, l_range, r_range);
    return root;
  }

  std::vector<Node*> GetAllNodes(int from, int to) {
    assert(l_range <= from && from <= to && to <= r_range);
    std::vector<Node*> all;
    std::function<void(Node*, int, int)> Dfs = [&](Node* x, int l, int r) {
      if (!x) return;
      if (from <= l && r <= to) {
        all.push_back(x);
        return;
      }
      PushDown(x);
      int m = l + (r - l) / 2;
      if (from <= m) Dfs(x->lch, l, m);
      if (to > m) Dfs(x->rch, m + 1, r);
    };
    Dfs(root, l_range, r_range);
    return all;
  }

  std::vector<Node*> GetPathNodes(int i) {
    assert(l_range <= i && i <= r_range);
    std::vector<Node*> all;
    Node* x = root;
    while (x) {
      all.push_back(x);
      if (x->l == x->r) break;
      int mid = (x->l + x->r) / 2;
      if (i <= mid) x = x->lch;
      else x = x->rch;
    }
    return all;
  }

  template <typename F>
  int GetFirstAfter(int p, F f) {
    assert(l_range <= p && p <= r_range);
    auto nodes = GetAllNodes(p, r_range);
    for (auto x : nodes) {
      if (f(x)) {
        while (x->r > x->l) {
          assert(f(x));
          PushDown(x);
          if (x->lch && f(x->lch)) {
            x = x->lch;
          } else {
            x = x->rch;
          }
        }
        return x->l;
      }
    }
    return -1;
  }

  template <typename F>
  int GetLastBefore(int p, F f) {
    assert(l_range <= p && p <= r_range);
    auto nodes = GetAllNodes(l_range, p);
    reverse(nodes.begin(), nodes.end());
    for (auto x : nodes) {
      if (f(x)) {
        while (x->r > x->l) {
          assert(f(x));
          PushDown(x);
          if (x->rch && f(x->rch)) {
            x = x->rch;
          } else {
            x = x->lch;
          }
        }
        return x->l;
      }
    }
    return -1;
  }

  template <typename F>
  void TraverseLeaf(Node* x, F f) {
    if (!x) return;
    if (x->l == x->r) {
      f(x);
      return;
    }
    PushDown(x);
    TraverseLeaf(x->lch, f);
    TraverseLeaf(x->rch, f);
  }

  template <typename F>
  void TraverseAllNode(Node* x, F f) {
    if (!x) return;
    f(x);
    if (x->l < x->r) PushDown(x);
    TraverseAllNode(x->lch, f);
    TraverseAllNode(x->rch, f);
  }

  template <typename F>
  static Node* BuildTree(int l, int r, F f) {
    Node* x = new Node(l, r);
    if (l == r) {
      f(l, x);
      return x;
    }
    int m = l + (r - l) / 2;
    x->lch = BuildTree(l, m, f);
    x->rch = BuildTree(m + 1, r, f);
    x->Update();
    return x;
  }

  void GC(Node* x) {
    if (!x) return;
    GC(x->lch);
    GC(x->rch);
    delete x;
  }
};

struct Info {
  multiset<int> data;
  auto Node() { return reinterpret_cast<SegmentTree<Info>::Node*>(this); }
  Info() {}
  bool NeedPushDown() { return false; }
  void PushDown() {}
  void Update() {}
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  SegmentTree<Info> seg(0, n - 1);
  seg.root = seg.BuildTree(0, n - 1,
                           [&](int i, Info* info) { info->data.insert(a[i]); });

  int q;
  cin >> q;
  vector<array<int, 3>> query(q);
  for (int i = 0; i < q; i++) {
    int op, l, r, x;
    cin >> op;
    if (op == 1) {
      cin >> l >> r >> x;
      l--, r--;
      query[i] = {l, r, x};
      seg.Modify(l, r, [&](Info* info) { info->data.insert(x); });
    } else if (op == 2) {
      cin >> x;
      x--;
      seg.Modify(query[x][0], query[x][1], [&](Info* info) {
        info->data.erase(info->data.find(query[x][2]));
      });
    } else {
      cin >> x;
      x--;
      int ans = 0;
      for (auto node : seg.GetPathNodes(x)) {
        if (!node->data.empty()) {
          ckmax(ans, *prev(node->data.end()));
        }
      }
      cout << ans << '\n';
    }
  }

  return 0;
}

Submission Info

Judge Result