感觉怎么写都是 $O(n \log^2 n)$ 啊qaq

卡了好久 $900 \mathrm{ms}$ AC，和题解差不多的样子qaq

或者有可能本人写的就是 $O(n \log n)$，只是不会证明（？）

namespace Main::Main {
  static constexpr const lu N(2e5);
  struct node {
    class segment_tree {
      struct node {
        lu size; node* d[2]; node() : size() { d[1] = d[0] = nullptr; } compl node() { clear(); }
        inline void clear() { size = 0; for (const hu d: { 0, 1 }) if (this->d[d]) this->d[d]->~node(), free(this->d[d]), this->d[d] = nullptr; }
        inline node*& dau(node*& d) { if (not d) d = &(*(node*)malloc(sizeof(node)) = node()); return d; }
        void insert(const lu t, const lu l = 1, const lu r = N)
        { ++size; if (l not_eq r) t <= (l + r) / 2 ? dau(d[0])->insert(t, l, (l + r) / 2) : dau(d[1])->insert(t, (l + r) / 2 + 1, r); }
        lu query(const lu t, const lu l = 1, const lu r = N) const {
          return l == r ? 0 :
            t <= (l + r) / 2 ? d[0] ? d[0]->query(t, l, (l + r) / 2) : 0 : (d[0] ? d[0]->size : 0) + (d[1] ? d[1]->query(t, (l + r) / 2 + 1, r) : 0);
        }
        void get(lu (&a)[N], lu& c, const lu l = 1, const lu r = N) const
        { if (l == r) { if (size) a[c++] = (l + r) / 2; } else { if (d[0]) d[0]->get(a, c, l, (l + r) / 2); if (d[1]) d[1]->get(a, c, (l + r) / 2 + 1, r); } }
        inline void merge(node& x) { size += x.size; for (const hu d: { 0, 1 }) if (x.d[d]) dau(this->d[d])->merge(*x.d[d]); }
        inline void merge(node& x, llu (&c)[2]) {
          size += x.size;
          for (const hu d: { 0, 1 }) if (x.d[d] and this->d[d ^ 1]) c[d ^ 1] += 1ull * x.d[d]->size * this->d[d ^ 1]->size;
          for (const hu d: { 0, 1 }) if (x.d[d]) dau(this->d[d])->merge(*x.d[d], c);
        }
      } root;
    public:
      segment_tree() : root() {} compl segment_tree() { clear(); } inline void clear() { root.clear(); } inline lu size() const { return root.size; }
      inline void insert(const lu x) { root.insert(x); } inline lu query(const lu x) const { return root.query(x); }
      inline void merge(segment_tree& x) { if (size() < x.size()) swap(*this, x); root.merge(x.root), x.clear(); }
      inline void merge(segment_tree& x, llu (&c)[2]) { c[1] = c[0] = 0, root.merge(x.root, c), x.clear(); }
      inline void get(lu (&a)[N], lu& c) const { root.get(a, c); }
    };
    segment_tree s; node* d[2]; node() : s() { d[1] = d[0] = nullptr; } compl node() { clear(); } inline lu size() const { return s.size(); }
    inline void clear() { s.~segment_tree(); for (const hu d: { 0, 1 }) if (this->d[d]) this->d[d]->~node(), free(this->d[d]), this->d[d] = nullptr; }
    inline void input() {
      const lu x(get<lu>());
      if (x) s.insert(x); else (d[0] = &(*(node*)malloc(sizeof(node)) = node()))->input(), (d[1] = &(*(node*)malloc(sizeof(node)) = node()))->input();
    }
    inline llu solve() {
      if (s.size()) { return 0; } llu res(d[0]->solve() + d[1]->solve()); if (d[0]->size() < d[1]->size()) { swap(d[0], d[1]); }
      /*static lu s[N]; lu c{}; d[1]->s.get(s, c);*/ static llu t[2]; // for (const lu* i(s); i < s + c; ++i) t += d[0]->s.query(*i);
      swap(this->s, d[0]->s), this->s.merge(d[1]->s, t); return res = res + min(t[0], t[1]);
    }
  };
  static lu n; node root;
  static inline void main() { get(n), root.input(), put(root.solve(), '\n'); }
}