题解 P5522 【[yLOI2019] 棠梨煎雪】
_虹_
2019-09-08 22:08:36
其实状压+线段树是很显然的。
主要难度在于合并区间信息。
三进制显然是不星的，O(nqlogm)比较危险（~~卡常神仙Orz~~），得想点办法在二进制下解决问题做到O(qlogm)。
具体解释写在代码里了。
| & ^这三个位运算居然不是同一个优先级。。。。。
```cpp
#include <iostream>
#include <string>
using namespace std;
struct unit{
int bit=0;//1 表示1 0表示0或pending
int pending=0;
};
struct node{
unit res;
int l,r;
};
inline int ls(int i)
{
return i<<1;
}
inline int rs(int i)
{
return ls(i)|1;
}
const int kmaxn=1000000+10+5;
const int failbit=1<<30;
node T[kmaxn<<2];
string rd[kmaxn];
unit merge(const unit& l,const unit& r)
{
unit res;
res.pending=l.pending & r.pending;
int cfm=l.pending ^ r.pending;//获取只有一方pending的bit，称为cfm bit
cfm=(l.bit | r.bit) & cfm;//对于一个cfm bit，因为l/r中有且只有一方确定了该位，而pending状态表示为0
//所以若l/r中有一方该位为1，则该位应为1（1&pending），否则为0（0&pending）
res.bit=l.bit | cfm;
if(res.bit ^ (r.bit | cfm))//双方将新确定的bit更新后不相同,说明有确定的bit不同，说明不存在复读机
res.bit|=failbit;
//当然也可以xor取出双方不同的bit和cfm bit比较，若存在一个1在cfm中不存在而双方xor中存在，则不存在复读机
//这个方法貌似更好想一点
/*
res.bit=l.bit | r.bit;
int dif=l.bit ^ r.bit;
if((dif|cfm) ^ cfm)
res.bit|=failbit;
*/
return res;
}
void upd(int p)
{
if(T[p].l==T[p].r)return;
T[p].res=merge(T[ls(p)].res,T[rs(p)].res);
}
unit init(int k)
{
unit res;
for(int i=0;i<rd[k].size();++i)
{
switch(rd[k][i])
{
case '0':
case '1':
res.bit+=(rd[k][i]-'0')<<i;
break;
case '?':
res.pending+=1<<i;
}
}
return res;
}
void build(int l,int r,int p=1)
{
T[p].l=l;T[p].r=r;
if(l==r)
{
T[p].res=init(l);
return;
}
int mid=(l+r)>>1;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
upd(p);
}
unit query(int l,int r,int p=1)
{
if(T[p].l==l&&r==T[p].r)
return T[p].res;
int mid=(T[p].l+T[p].r)>>1;
if(r<=mid)return query(l,r,ls(p));
else if(l>mid)return query(l,r,rs(p));
else
return merge(query(l,mid,ls(p)),query(mid+1,r,rs(p)));
}
void mod(int k,int p=1)
{
if(T[p].l==T[p].r)
{
T[p].res=init(k);
return;
}
int mid=(T[p].l+T[p].r)>>1;
if(k<=mid) mod(k,ls(p));
else mod(k,rs(p));
upd(p);
}
int n,q;
int opt,x,y;
int ans;
unit u;
inline int lowbit(int i)
{
return i&(-i);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>n>>q;
for(int i=1;i<=n;++i)
{
cin>>rd[i];
}
build(1,n);
// cout<<1<<endl;
while(q--)
{
cin>>opt>>x;
if(opt)
{
cin>>rd[x];
mod(x);
}
else
{
cin>>y;
u=query(x,y);
if(u.bit&failbit)
continue;
x=1;
// cout<<"pd "<<u.pending<<endl;
while(u.pending)
{
x<<=1;
u.pending-=lowbit(u.pending);
}
// cout<<x<<endl;
ans^=x;
}
}
cout<<ans<<endl;
return 0;
}
```
------------
~~什么神仙状压题~~