kazuma8128’s blog

競プロの面白い問題を解きます

Trie

k 番目に小さい値を取得可能な集合を管理するデータ構造

前提 配列(または bitset) Fenwick Tree 平方分割 Trie(動的 Segment Tree) 平衡二分木 おまけ 前提 集合に対して N 個の 追加・削除・k番目に小さい値の取得 のクエリがくるとします. 集合の要素は順序が付けられるものだけ考えます. 要素が非負整数の…

非負整数値を扱う Trie について

はじめに 非負整数を二分木のトライ木で管理するアレに関する日本語記事があんまり無いっぽいので雑にメモ. (というかそもそも専用の呼び名ないのかな?)とりあえずここでは Binary Trie って呼んどきます. Binary Trie とは 整数をビット列とみなしてトラ…

CodeChef GPD Gotham PD

問題文 https://www.codechef.com/problems/GPD 問題概要 頂点数 N の根付き木が与えられる. 各頂点には正整数のキーが付いている. 以下の二種類の Q 個のクエリをオンラインで処理せよ.クエリ1:頂点 v の子に, キー k の付いた新しい頂点 u を増やす クエ…