题解：CF558D Guess Your Way Out! II

tanghg · 2025-12-16 16:51:59 · 题解

不知道为什么紫。

考虑对于层 i 的操作 l,r，先将其转化为第 h 层对应的第几个叶子 L,R，显然是连续的。

之后对于真操作，我们可以转化成 [1,L-1],[R+1,n] 的假操作。那么就变成模拟了，动态开点线段树区间覆盖区间有值个数查询即可。对于说谎，显然为不存在没有被覆盖的位置。对于不确定，没被覆盖个数大于 1。对于确定，递归找输出即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
struct node{
    bool fm;ll sz;
    int l,r;
    #define lc(u) t[u].l
    #define rc(u) t[u].r
}t[MAXN*100];
void push_up(int u){
    t[u].fm|=(t[lc(u)].fm&&t[rc(u)].fm);
    t[u].sz=t[lc(u)].sz+t[rc(u)].sz;
}
int tot=0,rt;
void modify(int &u,ll l,ll r,ll ql,ll qr){
    if(!u){
        u=++tot;
    }
    if(ql<=l&&r<=qr){
        t[u].fm=true;
        t[u].sz=(r-l+1);
        return;
    }
    ll mid=(l+r)>>1ll;
    if(t[u].fm){
        if(!lc(u)){
            lc(u)=++tot;
        }
        if(!rc(u)){
            rc(u)=++tot;
        }
        if(lc(u)){
            t[lc(u)].fm=true;
            t[lc(u)].sz=mid-l+1;
        }
        if(rc(u)){
            t[rc(u)].fm=true;
            t[rc(u)].sz=r-mid;
        }
    }
    if(ql<=mid){
        modify(lc(u),l,mid,ql,qr);
    }
    if(mid+1<=qr){
        modify(rc(u),mid+1,r,ql,qr);
    }
    push_up(u);
}
ll sz(int u,ll l,ll r,ll ql,ll qr){
    if(!u){
        return 0;
    }
    if(ql<=l&&r<=qr){
        return t[u].sz;
    }
    ll mid=(l+r)>>1ll;
    if(t[u].fm){
        if(!lc(u)){
            lc(u)=++tot;
        }
        if(!rc(u)){
            rc(u)=++tot;
        }
        if(lc(u)){
            t[lc(u)].fm=true;
            t[lc(u)].sz=mid-l+1;
        }
        if(rc(u)){
            t[rc(u)].fm=true;
            t[rc(u)].sz=r-mid;
        }
    }
    ll ans=0;
    if(ql<=mid){
        ans+=sz(lc(u),l,mid,ql,qr);
    }
    if(mid+1<=qr){
        ans+=sz(rc(u),mid+1,r,ql,qr);
    }
    return ans;
}
ll ans;
int h;
void build(int u,ll l,ll r){
    if(t[u].fm){
        return;
    }
    if(l==r){
        cout<<l+((1ll<<h)-1-(1ll<<(h-1)))<<"\n";
        exit(0);
        return;
    }
    ll mid=(l+r)>>1ll;
    build(lc(u),l,mid);
    build(rc(u),mid+1,r);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int q;
    cin>>h>>q;
    ll n=(1ll<<(h-1)),al=1,ar=n;
    rep(i,1,q){
        int p,g;
        ll l,r;
        cin>>p>>l>>r>>g;
        while(p<h){
            ++p;
            l*=2;
            r=r*2+1;
        }
        l-=((1ll<<h)-1-(1ll<<(h-1)));
        r-=((1ll<<h)-1-(1ll<<(h-1)));
        if(g){
            if(ar<l||r<al){
                cout<<"Game cheated!"<<"\n";
                return 0;
            }
            al=max(l,al);
            ar=min(r,ar);
            if(al>1){
                modify(rt,1,n,1,al-1);
            }
            if(ar<n){
                modify(rt,1,n,ar+1,n);
            }
            if(sz(rt,1,n,al,ar)==ar-al+1){
                cout<<"Game cheated!"<<"\n";
                return 0;
            }
            continue;
        }
        modify(rt,1,n,l,r);

        if(sz(rt,1,n,al,ar)==ar-al+1){
            cout<<"Game cheated!"<<"\n";
            return 0;
        }
    }
    if(al==ar){
        cout<<al+((1ll<<h)-1-(1ll<<(h-1)))<<"\n";
        return 0;
    }
    if(t[1].sz!=n-1){
        cout<<"Data not sufficient!\n";
        return 0;
    }
    build(1,1,n);
    return 0;
}