题意：
给出n和q
表示有一棵深度为n的全然二叉树。叶子节点中有恰好一个点是出口 主角从根往下走。但不知道出口在哪里，但主角会获得q个提示。
像这样标号q个提示 格式： deep [l, r] ok
表示 深度为deep 时， 出口（可能在） （一定不在）[l,r]区间
ok=1表示 是可能在 ok=0一定不在
目标：
若依据提示能找到出口则输出叶子节点下标，有多个可能的出口则输出data not sufficient。若给出的提示互相矛盾输出 Game cheatde
思路：
首先把全部提示的区间都映射到叶子节点上
先把一定不在的问题转成2个一定存在的提示。
那么显然每一个提示里都包括了出口。所以我们查询一下哪个点是被q个区间覆盖了，则这个点就是出口。
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if (x>9) pt(x / 10);
putchar(x % 10 + '0');
}
typedef long long ll;
typedef pair<ll, ll> pii;
const int N = 500005;
const int inf = 1e9 + 10;
int n, q; ll L[55], R[55];
map<ll, int>mp;
int main() {
L[1] = R[1] = 1;
for (int i = 2; i <= 50; i++)L[i] = L[i - 1] << 1, R[i] = R[i - 1] << 1 | 1;
rd(n); rd(q);
if (q == 0) {
if (n == 1)puts("1");
else puts("Data not sufficient!");
return 0;
}
for (int i = 0, dep, ok; i < q; i++) {
ll l, r;
rd(dep); rd(l); rd(r); rd(ok);
while (dep < n) {
l <<= 1;
r = r << 1 | 1;
dep++;
}
if (ok)mp[l]++, mp[r + 1]--;
else {
mp[L[n]]++; mp[l]--;
mp[r + 1]++; mp[R[n]+1]--;
}
}
int sum = 0;
ll pre = -1, cnt = 0, ans = 0;
for (auto i : mp) {
sum += i.second;
if (pre != -1) {
cnt += i.first - pre;
ans = pre;
}
if (sum == q)pre = i.first;
else pre = -1;
}
if (cnt == 0)puts("Game cheated!");
else if (cnt > 1)puts("Data not sufficient!");
else pt(ans);
return 0;
}