[CF 558D] Guess Your Way Out! II

作法：

因為每次獲得的條件都形如：某個區間裡的數有其中一個是答案，或是這個區間裡都不是答案。而對於後者可以改寫成：答案落在兩個區間的聯集中。這樣就可以用以下算法解決：如果我們獲得了某個區間裡的數有其中一個是答案的條件，就把這個區間裡的每個數的值都$+1$，而對於另外一種條件我們也把「兩個聯集起來裡面有答案的線段」裡的數值都$+1$，那麼不難發現全部加完$1$之後那些值變成$Q$的就會是答案的候選人了（$Q$是條件個數）。因此就可以用離散化來做了，把區間加值轉換成在起點有個事件是$+1$，最後一個點的後一格有個事件是$-1$，排序後掃過去就可以知道答案了。

code :

#include<bits/stdc++.h>
#define LL long long
#define pii pair<LL,int>
#define F first
#define S second
using namespace std;
 
vector<pii> p ;
main()
{
    int h,Q ; scanf("%d%d",&h,&Q) ;
    LL ma=(1LL<<h)-1 ;
    for(int q=1;q<=Q;q++)
    {
        int h0,ans ; LL L,R ; scanf("%d%I64d%I64d%d",&h0,&L,&R,&ans) ;
        L=max((LL)L,1LL<<(h0-1)) ; R=min((LL)R,(1LL<<h0)-1) ;
        if(ans && R<L){printf("Game cheated!\n") ; return 0 ;}
        else if(R<L) continue ;
 
        LL L2=L*(1LL<<(h-h0)) , R2=(R+1)*(1LL<<(h-h0))-1 ;
        if(ans)
            p.push_back(pii(L2,1)) ,
            p.push_back(pii(R2+1,-1)) ;
        else
        {
            p.push_back(pii(1LL<<(h-1),1)) ;
            p.push_back(pii(L2,-1)) ;
            p.push_back(pii(R2+1,1)) ;
            p.push_back(pii(ma+1,-1)) ;
        }
    }
    p.push_back(pii(ma/2+1,1)) ;
    p.push_back(pii(ma+1,-1)) ;
    Q++ ;
    sort(p.begin(),p.end()) ;
    LL tmp=-1,ans=-1 ;
    bool mul=0 ;
    for(int i=0,now=0;i<p.size();)
    {
        int j=i ;
        while(j<p.size() && p[i].F==p[j].F)
            now+=p[j++].S ;
        if(now==Q)
        {
            if(ans!=-1) mul=1 ;
            else if(tmp==-1) tmp=p[i].F ;
        }
        else if(ans==-1 && tmp!=-1)
        {
            ans=tmp ;
            if(p[i].F==tmp+1) tmp=-1 ;
            else mul=1 ;
        }
        i=j ;
    }
    if(ans==-1) printf("Game cheated!\n") ;
    else if(mul) printf("Data not sufficient!\n") ;
    else printf("%I64d\n",ans) ;
}