//平行二分探索木 class BinarySearchTree<T> where T : IComparable<T> { class node { public node left = null; public node right = null; public T key = default(T); public node parent = null; public int height; } node root = null; bool change; int height(node t) => t?.height ?? 0; int bias(node t) => height(t.left) - height(t.right); void modHeight(node t) => t.height = 1 + Math.Max(height(t.left), height(t.right)); //vの左回転 node rotateL(node v) { var u = v.right; var t2 = u.left; u.left = v; u.parent = v.parent; v.parent = u; if (u.parent != null) if (u.parent.right == v) u.parent.right = u; else u.parent.left = u; else root = u; v.right = t2; if (t2 != null) t2.parent = v; modHeight(u.left); modHeight(u); return u; } //uの右回転 node rotateR(node u) { var v = u.left; var t2 = v.right; v.right = u;v.parent = u.parent;u.parent = v; if (v.parent != null) if (v.parent.right == u) v.parent.right = v; else v.parent.left = v; else root = v; u.left = t2;if (t2 != null) t2.parent = u; modHeight(v.right); modHeight(v); return v; } //tの二重回転(左→右) node rotateLR(node t) { t.left = rotateL(t.left); return rotateR(t); } //tの二重回転(右→左) node rotateRL(node t) { t.right = rotateR(t.right); return rotateL(t); } //挿入時の修正 node balanceLi(node t) => balanceL(t); node balanceRi(node t) => balanceR(t); //削除時の修正 node balanceLd(node t) => balanceR(t); node balanceRd(node t) => balanceL(t); //左部分木への挿入/右部分木での削除に伴う修正 node balanceL(node t) { if (!change) return t; var h = height(t); if (bias(t) == 2) { if (0 <= bias(t.left)) t = rotateR(t); else t = rotateLR(t); } else modHeight(t); change = (h != height(t)); return t; } //右部分木への挿入/左部分木での削除に伴う修正 node balanceR(node t) { if (!change) return t; var h = height(t); if (bias(t) == -2) { if (bias(t.right) <= 0) t = rotateL(t); else t = rotateRL(t); } else modHeight(t); change = (h != height(t)); return t; } public BinarySearchTree() { } //挿入 public void insert(T z) { change = true; _insert(new node() { key = z, height = 1 }); } void _insert(node z) { node y = null; node x = root; while (x != null) { y = x; if (z.key.CompareTo(x.key) < 0) x = x.left; else x = x.right; } if (y == null) { root = z; change = false; } else if (z.key.CompareTo(y.key) < 0) { y.left = z; y.left.parent = y; } else { y.right = z; y.right.parent = y; } //挿入に伴う修正 var s = z; while (s.parent != null) { if (s.parent.left == s) s = balanceLi(s.parent); else s = balanceRi(s.parent); } } //検索 public bool find(T v) { var n = _find(v); return n == null ? false : true; } node _find(T v) { var x = root; while (x != null) { if (x.key.CompareTo(v) == 0) return x; if (x.key.CompareTo(v) < 0) x = x.right; else x = x.left; } return null; } //削除 public void delete(T v) { change = true; _delete(_find(v)); } void _delete(node n) { if (n == null) return; if (n == root) { change = false; if (n.left == null && n.right == null) root = null; else if (n.left != null && n.right == null) { root = n.left; root.parent = null; } else if (n.left == null && n.right != null) { root = n.right; root.parent = null; } else { var next = n.right; while (next.left != null) next = next.left; n.key = next.key; change = true; _delete(next); } return; } var spl = n.parent.left; if (n.left == null && n.right == null) { if (n == n.parent.right) n.parent.right = null; else n.parent.left = null; } else if (n.left != null && n.right == null) { n.left.parent = n.parent; if (n == n.parent.right) n.parent.right = n.left; else n.parent.left = n.left; } else if (n.left == null && n.right != null) { n.right.parent = n.parent; if (n == n.parent.right) n.parent.right = n.right; else n.parent.left = n.right; } else { var next = n.right; while (next.left != null) next = next.left; n.key = next.key; _delete(next); } //削除に伴う修正 var s = n; while (s.parent != null) { if (spl == s) s = balanceLd(s.parent); else s = balanceRd(s.parent); spl = s.parent?.left; } } //vより一つ前の値を得る public bool prev(T v, ref T r) { var t = _find(v); if (null == t) return false; if (null != t.left) { t = t.left; while (t.right != null) t = t.right; r = t.key; return true; } while (t.parent != null) { if (t.parent.right == t) { r = t.parent.key; return true; } t = t.parent; } return false; } //vより一つ後の値を得る public bool next(T v, ref T r) { var t = _find(v); if (null == t) return false; if (null != t.right) { t = t.right; while (t.left != null) t = t.left; r = t.key; return true; } while (t.parent != null) { if (t.parent.left == t) { r = t.parent.key; return true; } t = t.parent; } return false; } }
参考
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (7件) を見る
背景
解説を読んで見て聞いて考え方はわかった。けど実装ができない。C++のsetみたいなのがあれば俺だってACできるのになー俺もなー。そんな経験はありませんか？ところで聞きました奥さん？setは二分木で実装されているんですって。というわけで作った。multisetが良かったけど今回はパス。
最初は「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の二分探索木(平衡でない)使ったけど後半でTLE。これは平衡にしてやる必要がありますねぇということで解説がわかりやすいとこ見つけてパクった参考にしました。無理やり混ぜ合わせたので結構怪しい。中身を理解できてるかも怪しい。いや怪しくないきっぱりと理解できていない曖昧なとこなどみじんもない堂々と胸を張って生きろ。まあACできたからいいや。いやよくない。今日のところはこれで勘弁してやる。
他の人の提出見ると巷でセグ木と呼ばれている暗黒魔術らしきものを使ってるっぽいけどよくわからない。雰囲気でふわふわ生きてるので。このままふわふわお空の底まで昇っていければいいのに。あ、昇っていくなら佐世保がいいな。今艦これのリアイベ中だし。佐世保ちょっと遠すぎるのですよね。片道8hておまえ。転職で福岡に移住とかありかもしれない。あと目からビーム出るようにならないかな。そしたら私はうれしい。
おまけ
static void Main(string[] args) { var N = Sarray()[0]; var P = Sarray(); var bst = new BinarySearchTree<long>(); var idx = new long[N]; for (long i = 0; i < N; ++i) idx[P[i] - 1] = i; long ans = 0L; for (var i = N - 1; 0 <= i; --i) { long ll = -1; long l = -1; long r = N; long rr = N; bst.insert(idx[i]); bst.prev(idx[i], ref l); bst.prev(l, ref ll); bst.next(idx[i], ref r); bst.next(r, ref rr); ans += (i + 1) * ((l - ll) * (r - idx[i]) + (rr - r) * (idx[i] - l)); } WriteLine(ans); }
