这道编程题用C++怎么做？

Question

现在有一款小游戏叫做“猜数游戏”。这个游戏的目的是从一个迷宫中找到一个出口。这个迷宫的形状是一棵高度为h的完全二叉树。玩家刚开始站在根部，出口是在某一个叶子结点上面。
现在我们来定义每一个结点的编号:
· 根部是1
· 某个内部结点的编号为 i (i ≤ 2h−1−1) 时，他的左儿子编号为2i，右儿子编号为2i+1。
根的深度定为1，其它结点的深度是他的父亲的深度+1。深度为h的结点是叶子。出口在某个叶子结点上，但是游戏玩家并不知道在哪个叶子，所以他现在要开始猜。
玩家每次会问ancestor(exit, i)属于[L,R]吗？这儿 ancestor(v, i) 表示结点v在第i层的那个祖先。然后游戏会给出"Yes"或"No"的回答。这个游戏的回答也不一定是完全合法的。有一些时候他会骗玩家。
现在有一些询问和回答，要求你从中判断一下，这个游戏有没有在说谎。如果游戏没有说谎，并且出口被推断出来，那么请输出出口，如果游戏没有说谎，但是出口不能被唯一判定出来，请输出“Data not sufficient!”。否则输出“Game cheated!”
结点u是结点v的祖先，当且仅当满足以下条件之一：
· u和v一样，
· u 是 v的父亲，
· u 是v的父亲的祖先。

样例解释：在这个例子中有 8个叶子结点。经过第一个询问之后，出口被确定在 [10, 14]区间内。经过第二个和第三个询问，只有14号符合条件。请结合图例进行理解。

Input
单组测试数据。
第一行有两个整数h, q (1 ≤ h ≤ 50, 1 ≤ q ≤ 10^5)，表示树的高度和询问的数量。
接下来q行，每行包含 i, L, R, ans (1 ≤ i ≤ h, 2^(i - 1) ≤ L ≤ R ≤ 2^i - 1, ans∈{0,1}),表示询问出口在第i层的祖先属于L，R吗？ans=1表示YES，否则表示NO。
Output
如果游戏给出的信息是自相矛盾的，那么输出 Game cheated!。
如果可以唯一确定出口。那么输出出口的编号。
否则输出Data not sufficient!。
Input示例
4 3
4 10 14 1
3 6 6 0
2 3 3 1
Output示例
14

Answer 1

思路：

1、对于每一个询问的区间【L，R】，因为知道区间所在的层数，所以可以求出最下面一层的区间【L'，R'】。比如在第x层的区间【L，R】
，那么在第x+1层的区间就为【L*2,R*2+1].

2、先求出所有询问的最下面一层的区间。

3、然后对这些区间按L从小到大排序。

4、遍历这些区间，维护ans=1/0的区间，如果存在ans=1的区间包含在ans=0的区间，则是矛盾的，反过来可以把ans=1的区间划分为三部分，
前面一部分区间不用考虑了，只需要维护最后面一部分区间就行，因为前面部分的区间已经可以确定了。

5、最后在判断一下ans=1的区间是不是多余1个就行了。