hack 线段树合并

RT，通过在“每次线段树合并垃圾回收无用空间”（也就是这里的做法）的做法空间复杂度并不是线性的。

我们构造一棵形如这样的二叉树：
一直这样长到 n 为之。

然后通过对输入边集顺序的构造，使得在 dfs 过程中每次都先访问右子树，这样就会导致在第一次合并操作开始前，所有叶子已经被访问到而插入了值，插入 \dfrac{n}{2} 次那么空间直接 \mathcal{O}(n\log n)，然后就爆了。

附一个输入数据生成器：

#include<bits/stdc++.h>
using namespace std;
const int n=1000000;
int main()
{
    cout<<n<<"\n";
    int m=n-1;
    int now=1,cnt=1;
    while(m)
    {
        cnt++;
        cout<<now<<" "<<cnt<<"\n";
        int nxt=cnt;
        m--;
        if(!m) break ;
        cnt++;
        cout<<now<<" "<<cnt<<"\n";
        now=nxt;
        m--;
    }
}

虽然 CF 题加不了 hack，但是无所谓了（