pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Binary Search Tree

CodeChef: Subtree swapping

codechef の practice ってあまり使わないので知らなかったんですが、コンテストから practice に問題が公開されるまで大分時間がかかるんですね。復習しづらい。 https://www.codechef.com/problems/SBSWAP オイラーツアーの切り貼りは、以下の記事で説明し…

CodeChef June Challenge 2016: Misha and Geometry

https://www.codechef.com/JUNE16/problems/MGCHGEOM 問題 以下の 2 種類のクエリが与えられる。 点(x, y) を追加する 点(x, y) を削除する クエリを順に処理し、処理するたびに凸包の面積を出力せよ。 クエリ数の合計は 105 以下

Educational Codeforces Round 13 F. Lena and Queries

http://codeforces.com/contest/678/problem/F 問題 以下の 3 種類のクエリを処理せよ。 点 (x,y) を set に追加する i 番目のクエリで追加した点を set から削除する xq+y の最大値を求める

HackerRank 101 Hack May 2016: Tree Splitting

www.hackerrank.com 完全制覇・ツリー上でのクエリ処理技法 - (iwi) { 反省します - TopCoder部 に書いてある euler tour tree と同じものだと思うけどどうなんだろう。 (追記:2016/06/25)本物の euler tour tree は全然違うものでした。 問題 n 頂点の…

Codechef April Challenge 2016

解法の概要だけ書いておきます。詳しい解説は書きません。