Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P5522 【[yLOI2019] 棠梨煎雪】

posted on 2019-09-08 22:08:36 | under 题解 |

其实状压+线段树是很显然的。

主要难度在于合并区间信息。

三进制显然是不星的,O(nqlogm)比较危险(卡常神仙Orz),得想点办法在二进制下解决问题做到O(qlogm)。

具体解释写在代码里了。

| & ^这三个位运算居然不是同一个优先级。。。。。

#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;
}

什么神仙状压题