g++拡張にpb_ds(policy based data structure)というのがあって、その中に便利なtreeというのがあります。
細かい使い方まとめみたいなページは見つかりませんでしたが、コンテストでの主な用法をまとめておきます。c++のsetの上位互換みたいな感じで使えます。
CF・TopCoderでは使えます。

用意:
g++の新しそうなやつを使う
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;

宣言:
tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_update> var_name;
いきなり長いです。さすがにtypedefするべき
keyに順序関係の定義された好きな型を入れてね

使えること:
setでできるものは大体できます。insert,erase,iterator関連・swapなど。
その他に使えるのが、いずれもO(logN)で

find_by_order 関数
- var_name.find_by_order(k) でk番目（0-indexed）のiteratorを返します。
order_of_key 関数
- var_name.order_of_key(key) でkey以上の最初の要素が、treeの中で何番目か返します。

が使えます。
このおかげで自前で何かを書く手間が省けるときもあるかも？

実は

split 関数
- var_name.split(key,tree) でkey以降の要素をtreeに移す
join 関数
- var_name.join(tree) でtreeを後ろにくっつける

という関数もありますが、どうやら変な実装のせいでO(N)かかるそうです。（少しテストしてみたところメチャクチャ遅かった）

同じkeyは複数保持できません。
null_type を別の型にすると、keyに紐付けされた別の要素を保存できます。

tree_order_statistics_node_updateのところを自前で欲しい要素を付け足した関数オブジェクトを書くと、例えば平衡二分探索木を使ったRMQなどが実現できますが、やっぱりsplitとjoinのせいで使え無さそう。

参考ページ
Implicit cartesian tree in GNU C++ STL. - Codeforces
C++ STL: Policy based data structures - Codeforces

2014-08-13

Codeforces Round #230 (Div. 1) E. Deleting Substrings

暗黒時代のCFなのはわかるがEditorialぐらい復活させてくれ :@
http://codeforces.com/contest/392/problem/E

概要

N要素からなる数列{w}がある。以下の操作を繰り返して、スコアを最大化せよ

数列の連続する部分を取り除き、その長さをLとすると、v[L]点稼げる。ただし、取り除く部分は隣接する項が絶対値で1ずつ異なっていて、山型でなければならない。(➚→➘)（操作が終わると、取り除かれた部分の左と右はくっつく。また、全部消さなくて途中で終わっても良い）

N<=400 , |v[i]|<=2000 w[i]<=10^9

解法

con[i][j]:=w[i],w[j-1]を公差1,-1の等差数列で結ぶとき、{w}の[i...j)で余ってしまうものを先に使うことになる。先に使うもののスコアの最大値
dp[i][j]:=w[i],w[j-1] を両端とする山型の形を作るときの、その範囲のスコアの最大値。{w}の[i...j)での山型の形の数列に入らないものは先にすべて使うことになる。
dp2[i][j]:={w}の[i...j)をすべて使うときのスコアの最大値。

このDPができると、
res[i]:=[0...i)までのスコアの最大値
をdp[i][j]を使って更新できる。

上のDPは、j-iが短い順にやると実はできる.
con[i][j]は、iの次のくるものを[i+1,j)の中で全部調べる。
dp[i][j]は、山のてっぺんになるものを[i,j)の中で全部調べる。
dp2[i][j]は、dp[i][j]を代入したあと、分割される場所を全部調べる。
時間O(n^3),空間O(n^2)
http://codeforces.com/contest/392/submission/7438155

2014-08-02

Codeforces Round #259 E. Little Pony and Lord Tirek

http://codeforces.com/contest/453/problem/E

問題概要:

ポニーがN匹一列に並んでいる。ポニーiは最初siのManaを持っており、毎時間riのペースでManaを増やすが、Manaはmiまでしか持てない（それ以上になるとmiで止まる）

クエリがM回ある。それぞれのクエリで、時刻tiに[l,r]の範囲のポニーのManaを全部刈り取り、その合計を答える。刈り取られると彼らのManaは0になる。

クエリーはtiが狭義単調増加になるよう与えられる。

解法

初期条件siは面倒なのでとりあえず無視。

セグメント木上の区間で、その区間に属するポニーを「刈り取られてからManaが増加する時間」の長さでソート。(mi/ri)
この並びのポニーで、miの累積和、riの累積和を取る。

これで、あるセグメント木上の区間が時刻Tに刈り取られ、その後時間difが経った時にまた刈り取られるとすると、増加時間が dif以上、以下でポニーを分割し、増加時間がdifより少ないポニーたちについてはmiの総和、大きいポニーたちについてはriの総和*difで刈り取る合計が求まる。①

クエリーごとに、刈り取る範囲のポニーの列を、いつ最後に刈り取られたかの区間で分割する。

いつ最後に刈り取られたかの区間について、セグメント木でlogN個の区間に分割できる。
区間K個と重なる範囲を刈り取るとすると、それぞれlogN個に分割し、①の方針でやると二分探索を含むのでO(Klog^2N)の時間がかかるが、刈り取る範囲に完全に含まれる区間は刈り取りの後全部一緒になる。ここから考えるとならしでO(Mlog^2N)になることが分かる。

いつ最後に刈り取られたかの区間はsetで持って重なるものをイテレーションしてもできるが、
以下の方法でもできる：
セグメント木上のあるノードに含まれるポニーが全員同じ時刻に刈り取られたなら、そこで①の感じで処理。
そうでないなら、刈り取る範囲に完全に含まれているとしても、さらに分割。

この方針で、刈り取られた時刻が同じ区間それぞれについて処理している事になる。

あるノードの刈り取られた時刻が一緒かどうかは、刈り取った時にそのノードにフラグを建てておき、下のノードへは使うときに伝播させる。あるノードを更新したら、それらの上のノードで刈り取られた時刻が同じかどうかを確認する、という一般的な処理。

初期条件siがあるので、最後に刈り取られたのが時刻0の場合は、何があってもノードがひとつになるまで分割。

時間O(Mlog^2N)
空間O(NlogN)

http://codeforces.com/contest/453/submission/7324878

2014-07-18

Codeforces Round #FF D. DZY Loves Games

http://codeforces.com/contest/446/problem/D

概要

N頂点M辺の無向連結グラフ(多重辺もたまにある)があり、ある頂点にいるときはつながっている辺を等しい確率で選んでその先に進む。
頂点にはtrapがあるかどうかが決まっている。
初め頂点1にいる。頂点1にはtrapはなく、頂点Nにはtrapがある。
trapのある頂点に進むと体力が1減る。体力が2の状態で頂点Nにたどり着く確率を求めよ。初めの体力はk

解法

ガウスの消去法+行列累乗
O(N^3+a^3logN) (aはtrap付きの頂点の数)
頂点iからどこかのtrap付き頂点にたどり着くまでのステップを考えると、
j(trapつき)へたどり着く確率P(i,j)は
P(i,j)=ΣP(隣接する頂点,j)/degree[i]
trap付き頂点については、
P(j,j)=1
P(k,j)=0 (j!=k , kにトラップがある)
としておく。

ここで、jがどの頂点でも、trap付きの頂点の式の定数項が変わるだけなので、
trap付き頂点の式の定数項をあたかも変数のように持っておき、その変数に対する係数をもつ。
その情報を含んだn*(2*n)行列でgauss-jordanする。
実際に値を求めるときはjに応じてこの変数を決め、係数を掛ける。

iからtrapのある頂点jに進むとき、
iがtrap付きなら、iの隣接する点たちからjまで進む確率の総和を次数で割る。
iがtrap無しなら、ふつうに。

あとは行列累乗をするだけ。k-1回目のtrapのvisitでNにたどり着けばいい。

http://codeforces.com/contest/446/submission/7145122