D. Guess Your Way Out! II
Problem's Link: http://codeforces.com/problemset/problem/558/D
Mean:
一棵满二叉树，树中某个叶子节点是出口，目的是寻找这个出口。再给定Q个询问的结果，每个结果告诉我们在第i层中(l,r)覆盖的叶结点是否包含出口。
analyse:
基本思路：多个区间求交集。
具体实现：
对于每一个询问，把它转化到最底层。并且把不在(l,r)区间的询问改为在(最左边，l-1)和(r+1,最右边)的形式，这样一来全部都变成了在(l,r)区间的描述。
区间统计：
对左右区间起点和终点组成的集合进行排序。然后找到答案存在的区间，如果区间长度=1，答案唯一；长度>1，答案不唯一;长度=0，无解。
Trick:会爆int。
Time complexity: O(n)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-07-16-11.55 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; LL L[51], R[51]; int main() {ios_base::sync_with_stdio( false );cin.tie( 0 );L[1] = 1, R[1] = 1;for( int i = 2; i <= 50; ++i ) L[i] = L[i - 1] << 1, R[i] = ( L[i] << 1 ) - 1;int h, q;cin >> h >> q;if( q == 0 ){if( h == 1 ) puts( "1" );else puts( "Data not sufficient!" );return 0;}map<LL, int> mp;for( int i = 0; i < q; ++i ){LL level, left, right, type, gap;cin >> level >> left >> right >> type;gap = h - level;while( gap ){gap--;left <<= 1;right = ( ( right + 1 ) << 1 ) - 1;}if( type ){mp[left]++;mp[right + 1]--;}else{mp[L[h]]++;mp[left]--;mp[right + 1]++;mp[R[h] + 1]--;}}LL ans, sum = 0, ans_gap = 0, mid_pre = -1;map<LL, int>:: iterator it = mp.begin();for( ; it != mp.end(); ++it ){sum += ( it->second );if( mid_pre != -1 ){ans_gap += ( it->first ) - mid_pre;ans = mid_pre;}if( sum == q ) mid_pre = ( it->first );else mid_pre = -1;}if( ans_gap == 1 ) cout << ans << endl;else if( ans_gap > 1 ) puts( "Data not sufficient!\n" );else puts( "Game cheated!\n" );return 0; } /**/