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; } /* */
