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

作者: wjyyy 分类: Treap,与或异或,二进制,数据结构,解题报告 发布时间: 2018-09-11 15:56

点击量:13

 

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

题目背景

\(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;
}

说点什么

avatar
  Subscribe  
提醒
/* */