kyuri2.cpp

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);
        if (rand() % 30 != 0) {
          tr = split(tr, sz+1).first; //trのsizeは1個ずつ大きくなっていくはず
        } else {
          tr = split(tr, sz-1).second; // 1/30の確率で[sz-1, sz)を取るようにする
        }
    }

    //ここでtrはバランスが崩れまくっている(ことがある)はず
    printf("%d\n", tr.max_dps());

    return 0;
}