3311. ST

单点时限: 2.0 sec

内存限制: 256 MB

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*2rt*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$ 的线段树构建的线段中的最大编号。

输入格式

第一行为 $T(T\leq 200)$,数据的组数

接下来 $T$ 每行为一个整数 $n$ 为线段树的规模

保证 $40\%$ 的数据有 $1\leq n\leq 10^5$

保证 $1\leq n \leq 10^{18}$

输出格式

对于每组数据输出规模为 $n$ 的线段树中rt的最大值

样例

Input
4
4
5
6
7
Output
7
9
13
13

24 人解决,39 人已尝试。

31 份提交通过,共有 100 份提交。

5.2 EMB 奖励。

创建: 7 年,2 月前.

修改: 7 年,1 月前.

最后提交: 3 年,6 月前.

来源: 2017.7.30 少年宫集训 NOIP模拟赛

题目标签