[BZOJ4811]由乃的OJ

题目大意

给你一个有n个点的树,每个点的包括一个位运算opt和一个权值x,位运算有&,l,^三种,分别用1,2,3表示。
有修改和询问两种共m次操作。
每次询问包含三个数x,y,z,初始选定一个数v。然后v依次经过从x到y的所有节点,每经过一个点i,v就变成v opti xi,所以他想问你,最后到y时,希望得到的值尽可能大,求最大值?给定的初始值v必须是在[0,z]之间。
每次修改包含三个数x,y,z,意思是把x点的操作修改为y,数值改为z。
$k<=64$ $x,y,z<2^k$

Solution

其实就是在树上的带修的多次询问的起床困难综合症
那道题的方法就是对每一位看一下初值每一位填0和填1哪个更优。多次询问拿到树上就是树链剖分,对每一段连续的区间用线段树维护出初值每一位取0,取1后这一段区间这一位的值。这样的空间复杂度是$O(64n)$,时间复杂度是$O(nk{log_n}^2)$,光荣地TLE(MLE也有可能)。

考虑怎么把每一位的信息合并。其实只要初值是0和(2^k-1)后计算出来的答案是有用的。两种答案分别记为a0,a1。那么初值第i位取0的话,最后这一位就会得到a0的第i位;取1的话,最后得到a1的第i位。
这样我们只要计算a0和a1两个值,时间复杂度变为了$O(n{log_n}^2)$。现在只需思考怎样在线段树上维护这个值。叶子节点的信息非常显然。合并两个节点时,左右节点信息分别记为al0,al1,ar0,ar1。那么a0在左边变为1的位到右边会变为ar1,答案为$al0\And ar1$;a0在左边变为0的位到右边会变为ar0,答案为$(!al0)\And ar0$。所以$a0=(al0\And ar1)|((!al0)\And ar0)$。同理,$a1=(vx.a1\And vy.a1)|((!vx.a1)\And vy.a0)$。
剩下只剩下一些小小的细节了。比如u->v的链和v->u的链是不一样的。树剖要把两条链分开写,线段树也要维护一段区间的从左到右的值和从右到做的值。等等。

Code
#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
struct node{
    ull a0,a1;
}treel[800010],treer[800010];
int num,ti,po[200010],Next[400010],vet[400010],head[200010],hson[200010],size[200010],Top[200010],fa[200010],dfn[200010],x[200010],deep[200010],n,k,xx[200];
ull y[200010],MAXN;
void add(int u,int v)
{
    Next[++num]=head[u];
    head[u]=num;
    vet[num]=v;
}
void dfs1(int u,int fa)
{
    hson[u]=0;
    size[u]=1;
    deep[u]=deep[fa]+1; 
    for (int i=head[u];i;i=Next[i])
    {
        int v=vet[i];
        if (v!=fa) 
        {
            dfs1(v,u);
            if (!hson[u]||size[v]>size[hson[u]]) hson[u]=v; 
            size[u]+=size[v];
        }
    }
}
void dfs2(int u,int father,int top)
{
    dfn[u]=++ti,po[ti]=u;
    Top[u]=top;
    fa[u]=father;
    if (hson[u]) dfs2(hson[u],u,top);
    for (int i=head[u];i;i=Next[i])
    {
        int v=vet[i];
        if (v!=father&&v!=hson[u]) dfs2(v,u,v);
    }
}
node Merge(node vx,node vy)
{
    node V=(node){(vx.a0&vy.a1)|((~vx.a0)&vy.a0),(vx.a1&vy.a1)|((~vx.a1)&vy.a0)};
    return V;
}
void build(int l,int r,int t)
{
    if (l==r) 
    {
        if (x[po[l]]==1) treel[t]=treer[t]=(node){0,y[po[l]]};
        if (x[po[l]]==2) treel[t]=treer[t]=(node){y[po[l]],MAXN};
        if (x[po[l]]==3) treel[t]=treer[t]=(node){y[po[l]],(MAXN^y[po[l]])};
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,t<<1);
    build(mid+1,r,t<<1|1);
    treel[t]=Merge(treel[t<<1],treel[t<<1|1]);
    treer[t]=Merge(treer[t<<1|1],treer[t<<1]);
}
void modify(int l,int r,int t,int pos,int keyy/*操作*/,ull keyx/*数值*/)
{
    if (l==r)
    {
        if (keyy==1) treel[t]=treer[t]=(node){0,keyx};
        if (keyy==2) treel[t]=treer[t]=(node){keyx,MAXN};
        if (keyy==3) treel[t]=treer[t]=(node){keyx,(MAXN^keyx)};
        return;
    }
    int mid=(l+r)>>1;
    if (pos<=mid) modify(l,mid,t<<1,pos,keyy,keyx);
    else modify(mid+1,r,t<<1|1,pos,keyy,keyx);
    treel[t]=Merge(treel[t<<1],treel[t<<1|1]);
    treer[t]=Merge(treer[t<<1|1],treer[t<<1]); 
}
node queryl(int l,int r,int t,int x,int y)
{
    if (l==x&&y==r) return treel[t];
    int mid=(l+r)>>1;
    if (y<=mid) return queryl(l,mid,t<<1,x,y);
    if (x>mid) return queryl(mid+1,r,t<<1|1,x,y);
    return Merge(queryl(l,mid,t<<1,x,mid),queryl(mid+1,r,t<<1|1,mid+1,y));
}
node queryr(int l,int r,int t,int x,int y)
{
    if (l==x&&y==r) return treer[t];
    int mid=(l+r)>>1;
    if (y<=mid) return queryr(l,mid,t<<1,x,y);
    if (x>mid) return queryr(mid+1,r,t<<1|1,x,y);
    return Merge(queryr(mid+1,r,t<<1|1,mid+1,y),queryr(l,mid,t<<1,x,mid));
}
void Que(int u,int v,ull z)
{
    int flag=0;
    node ans1,ans2;
    ans1=ans2=(node){0,MAXN};
    while (Top[u]!=Top[v])
    {
        if (deep[Top[u]]>=deep[Top[v]])
        {
            ans1=Merge(ans1,queryr(1,n,1,dfn[Top[u]],dfn[u]));
            u=fa[Top[u]];
        }
        else
        {
            ans2=Merge(queryl(1,n,1,dfn[Top[v]],dfn[v]),ans2);
            v=fa[Top[v]];
        }
    }
    if (deep[u]>deep[v])
        ans1=Merge(ans1,queryr(1,n,1,dfn[v],dfn[u]));
    else ans1=Merge(ans1,queryl(1,n,1,dfn[u],dfn[v]));
    node ans=Merge(ans1,ans2);
    flag=1;
    for (int i=k;i>=1;i--)
    {
        if (flag)
        {
            if ((z>>(i-1))&1) 
            {
                if ((ans.a0>>(i-1))&1||(!((ans.a1>>(i-1))&1)))
                    xx[i]=(ans.a0>>(i-1))&1,flag=0;
                else xx[i]=(ans.a1>>(i-1))&1;
            }
            else
            {
                xx[i]=(ans.a0>>(i-1))&1;
            }
        }
        else
        {
            if ((ans.a0>>(i-1))&1||(!((ans.a1>>(i-1))&1))) xx[i]=(ans.a0>>(i-1))&1;
            else xx[i]=(ans.a1>>(i-1))&1;
        }
    }
    ull Ans=0;
    for (int i=k;i>=1;i--)
        Ans=(Ans<<1)+xx[i];
    printf("%llu\n",Ans);
}
int main()
{
    int m;
    scanf("%d%d%d",&n,&m,&k);
    MAXN=(((1ULL<<(k-1))-1)<<1)+1;
    for (int i=1;i<=n;i++)
    {
        scanf("%d%llu",&x[i],&y[i]);
    }
    for (int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs1(1,0);
    deep[1]=1;
    dfs2(1,0,1);
    build(1,n,1);
    int op;
    while (m--)
    {
        scanf("%d",&op);
        if (op==1)
        {
            int x,y;
            ull z;
            scanf("%d%d%llu",&x,&y,&z);
            Que(x,y,z);
        } 
        else
        {
            int x,y;
            ull z;
            scanf("%d%d%llu",&x,&y,&z);
            modify(1,n,1,dfn[x],y,z);
        }
    }
    return 0;
}

1 thought on “[BZOJ4811]由乃的OJ”

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注