icpc-snippet

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub EarthMessenger/icpc-snippet

:heavy_check_mark: Link Cut Tree
(lib/ds/lct.hpp)

Depends on

Verified with

Code

#pragma once
#include "lib/internal.hpp"
#include "lib/monoid/monoid_trait.hpp"

/**
 * @brief Link Cut Tree
 *
 * @tparam BM Bidir Monoid
 */
template <typename BM> struct LinkCutTree
{
  using S = typename BM::S;
  struct Splay
  {
    using ptr = Splay *;

    u32 size;
    bool reversed;
    S val, prod;
    ptr fa, ch[2];

    Splay()
        : size(0), reversed(false), val(BM::un()), prod(BM::un()), fa(nullptr),
          ch{nullptr, nullptr}
    {
    }
    Splay(const S &_val)
        : size(1), reversed(false), val(_val), prod(val), fa(nullptr),
          ch{nullptr, nullptr}
    {
    }

    void update()
    {
      size = 1;
      prod = val;
      for (auto c : ch) {
        if (!c) continue;
        size += c->size;
        prod = BM::op(prod, c->prod);
      }
    }

    void reverse()
    {
      reversed = !reversed;
      std::swap(ch[0], ch[1]);
      prod = BM::ts(prod);
    }

    void set(const S &v)
    {
      val = v;
      update();
    }

    void push()
    {
      for (auto c : ch) {
        if (!c) continue;
        if (reversed) c->reverse();
      }
      reversed = false;
    }

    u32 which_child() const { return fa->ch[1] == this; }

    bool is_root() const
    {
      return fa == nullptr || (fa->ch[0] != this && fa->ch[1] != this);
    }

    void rotate()
    {
      auto x = this;

      auto y = x->fa;
      auto z = y->fa;
      auto xci = which_child();
      y->ch[xci] = x->ch[xci ^ 1];
      if (x->ch[xci ^ 1]) x->ch[xci ^ 1]->fa = y;
      x->ch[xci ^ 1] = y;
      if (!y->is_root()) z->ch[y->which_child()] = x;
      y->fa = x;
      x->fa = z;

      y->update();
      x->update();
    }

    void splay()
    {
      push();
      while (!is_root()) {
        auto y = fa;
        if (y->is_root()) {
          y->push();
          push();
          rotate();
        } else {
          auto z = y->fa;
          z->push();
          y->push();
          push();
          if (y->which_child() == which_child()) y->rotate();
          else rotate();
          rotate();
        }
      }
    }

    ptr access()
    {
      ptr rp = nullptr;
      ptr cur = this;
      while (cur) {
        cur->splay();
        cur->ch[1] = rp;
        cur->update();
        rp = cur;
        cur = cur->fa;
      }
      splay();
      return rp;
    }

    void make_root()
    {
      access();
      reverse();
    }
  };

  using ptr = typename Splay::ptr;

  std::vector<ptr> ptrs;

  template <typename F> LinkCutTree(int n, F &&f) : ptrs(n)
  {
    for (int i = 0; i < n; i++) ptrs[i] = new Splay(f(i));
  }

  void link(int x, int y)
  {
    auto xp = ptrs[x], yp = ptrs[y];
    xp->make_root();
    xp->fa = yp;
  }

  void cut(int x, int y)
  {
    auto xp = ptrs[x], yp = ptrs[y];
    xp->make_root();
    yp->access();
    yp->ch[0] = xp->fa = nullptr;
  }

  S prod(int x, int y)
  {
    auto xp = ptrs[x], yp = ptrs[y];
    xp->make_root();
    yp->access();
    return yp->prod;
  }

  void set(int x, const S &v)
  {
    auto xp = ptrs[x];
    xp->splay();
    xp->set(v);
  }

  void multiply(int x, const S &v)
  {
    auto xp = ptrs[x];
    xp->splay();
    xp->set(BM::op(xp->val, v));
  }

  S get(int x) { return ptrs[x]->val; }
};
Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: lib/internal.hpp: line 4: #pragma once found in a non-first line
Back to top page