2017.7.30 少年宫集训 NOIP模拟赛

ST(Segment Tree)线段树是程序设计竞赛中十分常见的数据结构。最近少年宫的同学学习了这个常见的数据结构。

线段树一种通过分治和记录结果以空间换取时间的数据结构。它的构建代码如下：

struct SegmentTree {
    void build(long long rt, long long L, long long R) {
        if (L == R) {
            return;
        } else {
            long long mid = (L + R) / 2;
            build(rt * 2, L, mid);
            build(rt * 2 + 1, mid+1, R);
        }
    }
};

线段树将线段递归地进行拆分，在上述函数中rt代表当前线段的编号，L代表当前线段的左端点，R代表当前线段的右端点，mid是左右端点的平均值，以mid为界线将线段进行切分，切分出来的线段为当前线段的左右孩子，分别编号为rt*2和rt*2+1。调用build(1, 1, n)就能构建出维护1到n的线段树，递归构建出所有线段后，每条线段含有三个参数rt,L,R。

在实际编写线段树的过程中，需要预先给线段树分配空间，而空间的大小只和所有线段的rt的最大值有关。通过观察，我们会发现线段树中rt的最大值的增长不是均匀的，比如1到4的线段树rt的最大值为7，1到5的线段树rt的最大值为9而1到6和1到7的线段树rt的最大值为13。维护 $1-N$ 的线段树需要 $4N$ 大小的空间。

cdm想要知道 $1-n$ 的线段树构建的线段中的最大编号。