Create a gist now

Instantly share code, notes, and snippets.

@yosupo06 /kyuri.cpp
Last active Oct 30, 2015

What would you like to do?
int main() {
Tree tr = new Tree(); //trは1ノード
srand(time(NULL)); //このブロックは乱数を適当に消費するためにあります
int rn = rand();
for (int i = 0; i < rn; i++) {
int sz = tr.size();
tr = merge(tr, tr);
tr = split(tr, sz).first; //同じものをくっつけて分離するだけの意味のない動作
}
assert(tr.size() == 1);
//ここから本題
for (int i = 0; i < 100000; i++) {
int sz = tr.size();
tr = merge(tr, tr);
tr = split(tr, sz+1).first; //trのsizeは1個ずつ大きくなっていくはず
}
//ここでtrはバランスが崩れまくっている(ことがある)はず
printf("%d\n", tr.max_dps());
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment