けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

BIT

AtCoder ARC 068 E - Snuke Line (700 点)

こういうのを得意になるぞー!!! でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…

AtCoder ARC 101 D - Median of Medians (700 点)

今更前々回の ARC を見て、噂の 700-D Median of Medians を見てみたけど、これはJOI 2017 予選 F - L番目のK番目の数https://t.co/EEfPlJ18Tkとほぼ同じ問題な気がしたん。— けんちょん (@drken1215) 2018年9月6日 とは言え、完全に一緒ではなくて後半の議…

AtCoder ABC 106 D - AtCoder Express 2 (400 点)

いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 (ABC 106 D) M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が…

Codeforces 198 DIV1 D - Iahub and Xors

領域加算、領域和取得の両方に対応した二次元 BIT ライブラリを目指した 問題概要 N × N の盤面において以下の M 個のクエリに答えよ: 長方形領域 [x0, y0] × [x1, y1] の XOR 和を出力 長方形領域 [x0, y0] × [x1, y1] 全体に一様に値 v を XOR 加算 考えた…

AOJ 2842 たい焼きマスターと食べ盛り

二次元 BIT ライブラリ の verify をした 問題へのリンク 問題概要 H × W のプレートにたこ焼きを置いて焼いていく。配置されたたこ焼きは「焼き上がった」「まだ焼き上がっていない」の 2 つの状態を持つ。なお、たこ焼きは配置されてから焼き上がるまでの…

AOJ 2667 Tree

オイラーツアー第4弾!!! でもせっかくなので色んな方法で解いてみたのん!!! Euler ツアー クエリの平方分割 HL 分解 重心分解 (未、todo) 問題へのリンク 問題概要 頂点 0 を根とする頂点数 N の根付き木において以下の Q 個のクエリに答えよ。なお初…

yukicoder 399 動的な領主 (HL分解で通す)

さあ次はいよいよ HL分解の練習をするのん!!!!! 問題へのリンク 問題概要 N 頂点のツリーが与えられて以下の Q 個の操作を行う。初期状態では全頂点の値は 0 である。また最終的に出力する値 res の初期値も 0 とする 2 頂点 u, v 間のパス上に含まれる…

NJPC 2017 H - 白黒ツリー

オイラーツアー練習第二弾。 そして、これにて一応、ツリーの辺に重みがある場合にも対応できることとなった。 問題へのリンク 問題概要 頂点 1 を根とした頂点数 N の根付き木が与えられる。初期状態では各頂点に 0 か 1 の値が割り当てられている。以下の …

Codeforces 486 DIV1 B Petr and Permutations: パリティの典型題

TL 見て面白そうだったから解いてみたのん Codeforces 486 DIV1 B Petr and Permutations 問題概要 サイズ N の順列が与えられる。これは以下のいずれかによってつくられたものである。 Petr: (1, 2, ..., N) から出発して、ランダムに 2 要素を選んで swap …

yukicoder 649 ここでちょっとQK!

yukicoder 649 ここでちょっとQK! K は固定で与えられる。数の集合 S に対する以下の Q 個のクエリを処理してください。i 番目のクエリは以下のいずれかです。 タイプ 1: S に数 v[i] を追加する。 タイプ 2: S に含まれる数のうち K 番目に小さい数を答…