Submission #46651915

---

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;

namespace bst {

template <typename Tree, typename F>
void BuildTree(Tree& tree, int l, int r, F f) {
  std::function<typename Tree::Node*(int, int)> Build = [&](int l, int r) ->
      typename Tree::Node* {
        if (l > r) return nullptr;
        int mid = (l + r) / 2;
        typename Tree::info_t info;
        auto x = new typename Tree::Node();
        f(mid, x);
        x->lch = Build(l, mid - 1);
        x->rch = Build(mid + 1, r);
        return tree.Update(x);
      };
  tree.root = Build(l, r);
}

template <typename Tree, typename Cmp>
typename Tree::Node* Search(Tree& tree, Cmp cmp) {
  auto x = tree.root;
  while (x) {
    tree.PushDown(x);
    auto t = cmp(x);
    if (t < 0) {
      x = x->lch;
    } else if (t == 0) {
      return x;
    } else {
      x = x->rch;
    }
  }
  return nullptr;
}

template <typename Tree>
typename Tree::Node* SearchFirst(Tree& tree) {
  auto x = tree.root, y = x;
  while (x) {
    tree.PushDown(x);
    y = x;
    x = x->Lch;
  }
  return y;
}

template <typename Tree>
typename Tree::Node* SearchLast(Tree& tree) {
  auto x = tree.root, y = x;
  while (x) {
    tree.PushDown(x);
    y = x;
    x = x->rch;
  }
  return y;
}

template <typename Tree, typename Cmp>
std::pair<int, std::vector<typename Tree::Node*>> SearchPath(Tree& tree,
                                                             Cmp cmp) {
  auto x = tree.root;
  std::vector<typename Tree::Node*> res;
  int dir = -1;
  while (x) {
    tree.PushDown(x);
    res.push_back(x);
    auto t = cmp(x);
    if (t < 0) {
      x = x->lch;
      dir = -1;
    } else if (t == 0) {
      return {0, res};
    } else {
      x = x->rch;
      dir = 1;
    }
  }
  return {dir, res};
}

template <typename Info>
struct KthCmp {
  KthCmp(int k_) : k(k_) {}
  int k;
  auto operator()() {
    return [&](Info* info) {
      auto x = info->Node();
      int left = x->lch ? x->lch->size : 0;
      if (k <= left) return -1;
      if (k == left + 1) return 0;
      k -= left + 1;
      return 1;
    };
  }
};

template <typename Tree>
typename Tree::Node* SearchKth(Tree& tree, int k) {
  return Search(tree, KthCmp<typename Tree::info_t>(k)());
}

template <typename Tree, typename Cmp>
int GetRank(Tree& tree, Cmp cmp) {
  int less = 0;
  auto rank_cmp = [&](typename Tree::Node* x) {
    int left = x->lch ? x->lch->size : 0;
    int t = cmp(x);
    if (t == 0) {
      less += left;
    } else if (t > 0) {
      less += left + 1;
    }
    return t;
  };
  Search(tree, rank_cmp);
  return less + 1;
}

template <typename Tree, typename F>
void Traverse(Tree& tree, F f) {
  std::function<void(typename Tree::Node*)> Go = [&](typename Tree::Node* x) {
    if (!x) return;
    tree.PushDown(x);
    Go(x->lch);
    f(x);
    Go(x->rch);
  };
  Go(tree.root);
}

}

template <bool>
struct TreapNodeBase {};
template <>
struct TreapNodeBase<false> {};
template <>
struct TreapNodeBase<true> {
  int ts;
};

template <typename Info, bool persist = false>
struct Treap {
  using info_t = Info;

  struct Node : public Info, public TreapNodeBase<persist> {
    unsigned int priority;
    Node *lch, *rch;
    Node(int ts_ = 0) : lch(nullptr), rch(nullptr) {
      static std::mt19937 rng(0);
      priority = rng();
      if constexpr (persist) this->ts = ts_;
    }

    Node(Node* x, int ts) {
      *this = *x;
      if constexpr (persist) this->ts = ts;
    }
    void Set(const Info& info) { (Info&)(*this) = info; }
  };

  Node* Create() { return new Node(ts); }
  Node* Copy(Node* x) { return new Node(x, ts); }

  Node* root;
  int ts;
  Treap() : root(nullptr), ts(0) {}

  Node* Update(Node* x) {
    x->Update();
    return x;
  }
  void PushDown(Node* x) {
    if (x->NeedPushDown()) {
      if constexpr (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();
    }
  }

  Node* Join(Node* x, Node* y) {
    if (!x) return y ? Update(y) : nullptr;
    if (!y) return Update(x);
    if constexpr (persist) {
      if (x->ts != ts) x = new Node(x, ts);
      if (y->ts != ts) y = new Node(y, ts);
    }
    PushDown(x);
    PushDown(y);
    if (x->priority >= y->priority) {
      x->rch = Join(x->rch, y);
      return Update(x);
    } else {
      y->lch = Join(x, y->lch);
      return Update(y);
    }
  }

  Node* Join(Node* x, Node* y, Node* z) {
    if (!x) return Join(y, z);
    if (!y) return Join(x, z);
    if (!z) return Join(x, y);
    assert(!y->lch && !y->rch);
    if constexpr (persist) {
      if (x->ts != ts) x = new Node(x, ts);
      if (y->ts != ts) y = new Node(y, ts);
      if (z->ts != ts) z = new Node(z, ts);
    }
    PushDown(x);
    PushDown(z);
    if (x->priority >= y->priority && x->priority >= z->priority) {
      x->rch = Join(x->rch, y, z);
      return Update(x);
    } else if (y->priority >= z->priority) {
      y->lch = x;
      y->rch = z;
      return Update(y);
    } else {
      z->lch = Join(x, y, z->lch);
      return Update(z);
    }
  }

  template <typename Cmp>
  std::tuple<Node*, Node*, Node*> Split(Node* x, Cmp cmp) {
    if (!x) return {nullptr, nullptr, nullptr};
    if constexpr (persist) {
      if (x->ts != ts) x = new Node(x, ts);
    }
    PushDown(x);
    auto d = cmp(x);
    if (d == 0) {
      auto l = x->lch, r = x->rch;
      if constexpr (persist) {
        if (l && l->ts != ts) l = new Node(l, ts);
        if (r && r->ts != ts) r = new Node(r, ts);
      }
      x->lch = x->rch = nullptr;
      return {l, Update(x), r};
    } else if (d < 0) {
      auto [w, y, z] = Split(x->lch, cmp);
      x->lch = nullptr;
      return {w, y, Join(z, Update(x))};
    } else {
      auto [w, y, z] = Split(x->rch, cmp);
      x->rch = nullptr;
      return {Join(Update(x), w), y, z};
    }
  }

  auto SplitKth(Node* x, int k) { return Split(x, bst::KthCmp<Info>(k)()); }

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

double Random() {
  static mt19937 rng(0);
  static const uint mm = numeric_limits<uint>::max();
  return rng() * 1.0 / mm;
}

struct Info {
  int val, max_val, min_val, size, ran;
  auto Node() { return reinterpret_cast<Treap<Info>::Node*>(this); }
  Info() {}
  bool NeedPushDown() { return false; }
  void PushDown() {}
  void Update() {
    max_val = min_val = val;
    size = 1;
    auto lch = Node()->lch, rch = Node()->rch;
    if (lch) {
      ckmax(max_val, lch->max_val);
      ckmin(min_val, lch->min_val);
      size += lch->size;
    }
    if (rch) {
      ckmax(max_val, rch->max_val);
      ckmin(min_val, rch->min_val);
      size += rch->size;
    }
    ran = val;
    double t = Random();
    if (lch && t < 1.0 * lch->size / size) ran = lch->ran;
    else if (rch && t < 1.0 * ((lch ? lch->size : 0) + rch->size) / size)
      ran = rch->ran;
  }
};

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

  int n, q;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  Treap<Info> treap;
  bst::BuildTree(treap, 0, n - 1, [&](int i, Info* info) { info->val = a[i]; });

  cin >> q;
  vector<Treap<Info>::Node*> roots(q + 1);
  roots[0] = treap.root;

  auto SplitLarger =
      [&](auto self, Treap<Info>::Node* x,
          int val) -> pair<Treap<Info>::Node*, Treap<Info>::Node*> {
    if (!x) return {nullptr, nullptr};
    if (x->max_val <= val) return {x, nullptr};
    auto [t1, t2] = self(self, x->lch, val);
    auto [t3, t4] = self(self, x->rch, val);
    x->lch = x->rch = nullptr;
    x->Update();
    if (x->val > val) return {treap.Join(t1, t3), treap.Join(t2, x, t4)};
    else return {treap.Join(t1, x, t3), treap.Join(t2, t4)};
  };

  auto SplitSmaller =
      [&](auto self, Treap<Info>::Node* x,
          int val) -> pair<Treap<Info>::Node*, Treap<Info>::Node*> {
    if (!x) return {nullptr, nullptr};
    if (x->min_val > val) return {nullptr, x};
    auto [t1, t2] = self(self, x->lch, val);
    auto [t3, t4] = self(self, x->rch, val);
    x->lch = x->rch = nullptr;
    x->Update();
    if (x->val <= val) return {treap.Join(t1, x, t3), treap.Join(t2, t4)};
    else return {treap.Join(t1, t3), treap.Join(t2, x, t4)};
  };

  for (int i = 1; i <= q; i++) {
    int t, s, x;
    cin >> t >> s >> x;
    if (t == 1) {
      auto [t1, t2, t3] = treap.SplitKth(roots[s], x);
      roots[s] = treap.Join(t1, t2);
      roots[i] = t3;
    } else {
      Treap<Info>::Node *t1, *t2;
      if (roots[s] && roots[s]->ran >= x) {
        tie(t1, t2) = SplitSmaller(SplitSmaller, roots[s], x);
      } else {
        tie(t1, t2) = SplitLarger(SplitLarger, roots[s], x);
      }
      roots[s] = t1;
      roots[i] = t2;
    }
    int num = roots[i] ? roots[i]->size : 0;
    cout << num << '\n';
  }

  return 0;
}

Submission Info

Judge Result