Binary Indexed Tree

No.728 ギブ and テイク - yukicoder

i<jとする。 (i, j)が満たしたい条件は A[i]+R[i]>=A[j]かつA[i]>=A[j]-L[j] jをループで固定する。jを昇順に見ていくならば A[i]+R[i]>=A[j]を満たすiはjが増加するごとに条件がきつくなる。 なのでi<jについて A[i]+R[i]の値を優先順位度付きキューで持っておいて、 A[i']+R[i']<A[j]となるような添え字i'を取り除いていく。 あとはA[i]>=A[j]-L[j]であるが、 取り除いたあとに残っているすべてのi</jについて></jとする。>

D: Median of Medians - AtCoder Regular Contest 101 | AtCoder

中央値がxの場合=>中央値がx以上の場合 f(x) := 「x以上の値が中央値となる連続部分列の個数」とする。 ここで部分列がH(N, 2)個あるので、そのちょうど真ん中になるのが中央値。 つまり f(x) >= ceil(H(N, 2)/2) を満たす最大のxが解。fは単調増加なので二…

Manhattan Center (manhattan-center) | CSA

与えられた頂点のK個からなる部分集合について、最適なPの座標はx座標の中央値となる。 なので、Pの候補は与えられた頂点のx座標に限られる。 これらx座標を昇順に見ていく。(以下、x[k]<x[k+1]とする) P=x[0]としてとりあえず近いK個を集合Lに入れておく。残った頂点は集合Rに入っているとする。 x[k] -> x[k+1]と変化したとする。x[k]のときの最適な構成Lから、x[k+1]のとき</x[k+1]とする)>…

E2. Median on Segments (General Case Edition) | Codeforces Round #496 (Div. 3)

f(x) を「中央値をxとする部分文字列の数」とする。f(m)が解。 とおくと を得る。 あとは、g(y)を求めるだけ。g(y)の値は、中央値がy以上の部分文字列の数を表す。 部分文字列の中央値がy以上である必要十分条件は (y以上の値の数)>=(y未満の値の数) とわか…

Marked Ancestor (AOJ 2170, JAG Summer 2009)

ライブラリがあれば楽にとけるやつ。HL分解して、マークしたかどうかはBinary Indexed Treeなどを使うだけ。 vector<vi> G(N); FOR(i, 1, N) { int p; cin >> p; --p; G[p].push_back(i); } HLDecomposition hld(G); // 0ならばマークされていない。 // そうでな</vi>…

B. Petr and Permutations | Codeforces Round #485 (Div. 1)

転倒数の偶奇は操作回数のそれと等しい。 とおく。 l番目の要素とr番目の要素を交換したとする。 l番目とr番目の間にz個の要素があるとする。 また、そのうち、もとのl番目より大きい要素をgL個, 小さい要素をlL(=z-gL)個とする。 まずl番目と間z個の関係だ…

E - Sorted and Sorted | AtCoder Regular Contest 097

隣接要素同士の交換しかできないのだから、もし白または黒のみであれば、最小の操作回数は転倒数に等しい。 この問題では、白と黒の2色の並び方ごとに操作回数が異なる。しかし、白と黒の並びが定まれば、操作回数は一意に定まる。なぜなら、各並び方につい…

yukicoder #568: じゃんじゃん 落とす 委員会

SAの値が決まっているとする。 f[i](l,r)をB以外の問題について正答数がiとしたときのl<=B[j]

Codeforces #413 E: Aquarium decoration

解説付きコード /* 解説 二人とも好むアイテムの集合をX, MashaだけのはY, ArkadyだけのはZとする 全体でちょうどm個でなければならないが、とりあえずそのことは考えない。 Xからx個選ぶとする。xは|X|から0まで総当りする。 k-x個だけYとZから取る必要があ…