データ構造に関するカテゴリーです。

AtCoder,データ構造

問題方針セットとマップによる値の管理

まず初めに、セットに \( 1 \) から \( M \) までの値を入れます。次に、先頭から \( M \) 個までの \( M \) 未満の値の頻度をマップで管理します。このとき現れた値をセット ...

AtCoder,データ構造

問題方針

各要素同士の差の \( 2 \) 乗の和を求めるために、\( A_i \) の頻度を数えます。

コード#include <bits/stdc++.h>using namespace std;typedef long ...

AtCoder,平方分割

問題方針

\( x = A_i \) としたとき、\( i – 1\) 番目から先頭に向かって、\( A_i \leq A_j \) を連続的に満たす \( j \) の個数を \( a \) とします。また、\( i + ...

AtCoder,データ構造,文字列

問題方針

括弧の対応の問題で良く使うスタックを使います。スタックに \( s \) の先頭から入れていき、\( s_i = o \) のとき、スタックの先頭から “xf” と積まれていたら “fox& ...

AtCoder,セグメント木,動的計画法

問題方針

最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。

まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...

Codeforces,フェニック木

問題方針

バブルソートを行った回数を求めるために、フェニック木 (BIT) を使います。詳しくは下記の参考を参照してください。

コード#include <bits/stdc++.h>using namespace std;t ...

AtCoder,動的計画法,累積和,遅延評価セグメント木

問題方針遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...

yukicoder,セグメント木,数学

問題方針

関節 \( i \) の位置を \( P_i = (x_i, y_i) \) とします。初期値は、\( P_i = (i, 0) \) となり、\( P_0 = (0, 0) \) となります。ここで、ベクトル  \ ...

AtCoder,データ構造,実装

問題方針

ある集合の最大値を管理し、その集合の最大値の中の最小値を答える問題です。これは、multiset を使って管理できるそうです。multiset は順序が保たれます。

ここで、幼稚園 \( i \) のレートの集合を ...

AtCoder,セグメント木

問題方針

区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメ ...