题解 CF558D 【Guess Your Way Out! II】
SIGSEGV
2020-04-12 17:25:30
首先预处理出每一层的结点编号范围，然后处理每一个询问时先将$L$和$R$的范围缩小到$i$层的编号范围内(即取交集)，然后对$L$和$R$映射到$h$层的位置进行差分，在符合本次询问的点的位置处+1。最后统计有多少个位置的值是$q$即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 400005;
using ll = long long;
int h,q,idx,ptr;
ll idl[N],idr[N];
struct Query {ll pos;int v;} d[N],dd[N];
ll lleaf(ll num)
{
while (idl[h] > num) num = num << 1;
return num;
}
ll rleaf(ll num)
{
while (idl[h] > num) num = num << 1 | 1;
return num;
}
int main ()
{
ios::sync_with_stdio(false);
cin >> h >> q;
idl[1] = idr[1] = 1;
for (int i = 2;i <= h;i++) idl[i] = idl[i - 1] << 1,idr[i] = idr[i - 1] << 1 | 1;
int t1,op;ll t2,t3;
d[++idx] = {idl[h],0};d[++idx] = {idr[h] + 1,0};
for (int i = 1;i <= q;i++)
{
cin >> t1 >> t2 >> t3 >> op;
t2 = max(t2,idl[t1]);t3 = min(t3,idr[t1]);
if (op == 1)
{
d[++idx] = {lleaf(t2),1};d[++idx] = {rleaf(t3) + 1,-1};
}
else
{
d[++idx] = {idl[h],1};d[++idx] = {lleaf(t2),-1};
d[++idx] = {rleaf(t3) + 1,1};d[++idx] = {idr[h] + 1,-1};
}
}
sort(d + 1,d + idx + 1,[](Query a,Query b) {return a.pos < b.pos;});
for (int i = 1;i <= idx;i++)
if (i == 1 || d[i].pos != d[i - 1].pos) dd[++ptr] = d[i];
else dd[ptr].v += d[i].v;
ll cnt = 0,ans = 0;int cur = dd[1].v;
for (int i = 2;i <= ptr;i++)
{
ll diff = dd[i].pos - dd[i - 1].pos;
if (cur == q) cnt += diff,ans = dd[i - 1].pos;
cur += dd[i].v;
}
if (cnt > 1) cout << "Data not sufficient!" << endl;
else if (cnt == 1) cout << ans << endl;
else cout << "Game cheated!" << endl;
return 0;
}
```