洛谷 P4883 mzf的考验 题解【平衡树】【二进制】【与或异或】

点击量：186

    感觉比较麻烦但是还是比较简单的好题。

目录

题目背景

\(mzf\)立志要成为一个豪杰，当然，他也是一个\(OIer\)。 他希望自己除了会\(OI\)之外还会各种东西，比如心理学、吉他、把妹等等。 为了让自己有更大的魅力，他不驼背，不熬夜，整天锻炼，双目炯炯有神，是我们机房最不像\(OIer\)的人。 然而，在与我们格格不入若干天并且将《易经》研究透彻之后，承受不住我们对他另类的言论，他爆发了。 机房在那一刹那仿佛天塌地陷，世界末日。

 

题目描述

八卦有乾、坤、震、巽、坎、离、艮、兑； 两两组合，一上一下，形成了六十四卦，每卦六爻，一共三百八十四爻。 爻分阴阳，阳爻性属阳刚，阴爻性属阴柔。天下之大，无奇不有。千奇百怪，皆出此处。\(mzf\)研究透彻了易经之后，画出了\(n\)个奇怪的图案。他说那是他改进出来的更强大的卜卦体系。 每一个图案有二十行，每一行要么是阴爻\((0)\)，要么是阳爻\((1)\)，作为一个\(OIer\)，我们可以将卦象看成一个个二进制串； 他将\(n\)个图案画在了符纸上，然后进行\(m\)次操作：

 

操作\(1\)：翻转区间\([l,r]\)的图案，比如\((3,1,2,5)\)变成\((5,2,1,3)\)；

 

操作\(2\)：\(mzf\)画地为卦，将\([l,r]\)之间的卦象都异或上新画的那个卦象；

 

操作\(3\)：\(mzf\)会询问机房里的其他人[l,r][l,r]之间卦象代表的二进制数权值和。

 

如果不能正确回答每个操作\(3\)，那么机房风水格局将会改变，我们都将…！

 

由于\(mzf\)疯狂之下将我们都捆♂绑♂了起来，所以只能求求你来帮我们解决这个问题。

 

输入输出格式

输入格式：

第一行两个正整数：\(n\)，\(m\)（\(n\)为序列长度，\(m\)为操作个数）

 

第二行\(n\)个正整数：\(a[i]\) (用\(10\)进制数表示每个卦象)\((1\le i\le n)\)

 

接下来\(m\)行：每行首先一个正整数\(opt\)表示操作类型

 

\(opt==1\)：两个正整数：\(l,r\)。请翻转区间\([l,r]\)；

\(opt==2\)：三个正整数：\(l,r,d\)。请将区间\([l,r]\)中的所有卦象都异或卦象\(d\)。\((0\le d\le 10^5)\)

\(opt==3\)：两个正整数：\(l,r\)。请查询区间\([l,r]\)的卦象权值和。

 

输出格式：

对于每个\(opt==3\)的情况，输出一行答案。

 

输入输出样例

输入样例#1：

8 9
4 6 2 1 7 9 10 2
1 1 4
3 1 6
2 4 5 2
3 1 6
2 1 5 8
3 1 6
2 5 7 10
3 4 7
3 1 8

输出样例#1：

29
29
69
24
59

说明

对于\(20\%\)的数据，\(n\le 1000,m\le 1000\)，

 

对于另外\(20\%\)的数据，不存在操作\(1\)，

 

对于另外\(20\%\)的数据，保证\(n\)为\(2\)的次幂，且在操作\(1\)中，保证\(l=i\times 2^j+1,r=(i+1)\times 2^j\)，其中\(i,j\)为任意值，

 

对于\(100\%\)的数据，\(n\le 10^5,m\le 5\times 10^4,1\le l\le r\le n,0\le d<2^{20}\)

题解：

    首先对于这么多区间操作，可以知道应该使用线段树或平衡树这样的数据结构。但是线段树不支持区间反转，因此考虑平衡树。因为\(d\le 2^{20}\)，所以我们开\(20\)棵平衡树就可以了。但是这样常数会很大，反转和维护要进行很多次。因此多棵平衡树不可行。

    考虑这个题需要对区间进行异或，但是异或操作无法直接获取并修改区间结果，因此每个节点不能存子树的权值和。而为了异或方便，可以在每个节点存子树中所有的数，第\(i\)位有多少个1。每次进行异或就把每一位（假设有\(m\)个1）变成\(size-m\)，就达到了异或的效果。同时只用到了一棵平衡树。

    而平衡树可以方便地随时维护子树信息，并且可以完成反转操作。不过因为每个节点还代表一个数，所以还要额外存自己的状态，在进行异或操作时要把自己本身存的信息也取反。

    所以在调整树的结构时，任何一步操作都要maintain并pushdown，这样才能保证信息转移的层次和正确性。时间复杂度\(O(n\log^2n)\)（把20近似为\(\log n\)）。

Code(O2)：

#include<cstdio>
#include<cstdlib>
#include<cstring>
struct node
{
    int sz,rdm;
    int key[21],lazy[21],now[21];
    //key是总共的,now是自己的
    int rev;//是否需要反转
    node *ls,*rs;
    node(int x)
    {
        int t=0;
        sz=1;
        rev=0;
        rdm=rand();
        memset(lazy,0,sizeof(lazy));
        ls=NULL;
        rs=NULL;
        for(int i=0;i<=20;++i)
        {
            if(x&1)
            {
                now[t]=1;
                key[t]=1;
            }
            else
            {
                now[t]=0;
                key[t]=0;
            }
            x>>=1;
            ++t;
        }
    }
    node()
    {
        memset(lazy,0,sizeof(lazy));
        memset(key,0,sizeof(key));
        memset(now,0,sizeof(now));
        rev=0;
        ls=NULL;
        rs=NULL;
    }
    void maintain()
    {
        sz=(ls?ls->sz:0)+(rs?rs->sz:0)+1;
        for(int i=0;i<=20;++i)
            key[i]=(ls?ls->key[i]:0)+now[i]+(rs?rs->key[i]:0);
    }
    void pushdown()
    {
        if(rev)
        {
            rev=0;
            node *tmp=ls;
            ls=rs;
            rs=tmp;
            if(ls)
                ls->rev^=1;
            if(rs)
                rs->rev^=1;
        }
        for(int i=0;i<=20;++i)
            if(lazy[i])//第i位需要异或
            {
                lazy[i]=0;
                if(ls)
                {
                    ls->lazy[i]^=1;
                    ls->now[i]^=1;
                    ls->key[i]=ls->sz-ls->key[i];
                }
                if(rs)
                {
                    rs->lazy[i]^=1;
                    rs->now[i]^=1;
                    rs->key[i]=rs->sz-rs->key[i];
                }
            }
    }
}*root;
node *Merge(node *a,node *b)
{
    if(!a||!b)
        return a?a:b;
    a->pushdown();
    b->pushdown();
    if(a->rdm<b->rdm)
    {
        a->rs=Merge(a->rs,b);
        a->maintain();
        return a;
    }
    b->ls=Merge(a,b->ls);
    b->maintain();
    return b;
}
void split(node *rt,int x,node *&a,node *&b)
{
    if(!rt)
    {
        a=NULL;
        b=NULL;
        return;
    }
    rt->pushdown();
    int ls=rt->ls?rt->ls->sz:0;
    if(x>ls)
    {
        a=rt;
        split(a->rs,x-ls-1,a->rs,b);
    }
    else
    {
        b=rt;
        split(b->ls,x,a,b->ls);
    }
    rt->maintain();
    return;
}
int main()
{
    int n,m,u,op,v,w;
    long long sum;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&u);
        root=Merge(root,new node(u));
    }
    node *a,*b,*c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&u,&v);
            split(root,u-1,a,b);//提取区间
            split(b,v-u+1,b,c);
            b->rev^=1;
            root=Merge(Merge(a,b),c);
        }
        else if(op==2)
        {
            scanf("%d%d%d",&u,&v,&w);
            split(root,u-1,a,b);
            split(b,v-u+1,b,c);
            for(int j=0;j<=20;++j)
                if((w>>j)&1)
                {
                    b->key[j]=b->sz-b->key[j];
                    b->lazy[j]^=1;
                    b->now[j]^=1;
                }
            root=Merge(Merge(a,b),c);
        }
        else
        {
            scanf("%d%d",&u,&v);
            split(root,u-1,a,b);
            split(b,v-u+1,b,c);
            sum=0;
            for(int j=0;j<=20;++j)
                sum+=(long long)b->key[j]*(1<<j);
            printf("%lld\n",sum);
            root=Merge(Merge(a,b),c);
        }
    }
    return 0;
}