黑白棋 题解【平衡树】【线段树】【前缀和】

作者: wjyyy 分类: Treap,与或异或,二进制,线段树,解题报告 发布时间: 2019-05-05 09:29

点击量:32

数据结构好题。学会了平衡树代替权值线段树(雾

题目描述

黑白棋的棋盘有 $N$ 行 $M$ 列,而且这 $N\times M$ 个位置上全部都放好了棋。棋的正面为白色,反面为黑色。我给这个棋盘的每行每列都施展了一个魔法,总共 $N+M$ 个魔法。每当一个魔法被触发的时候,会将对应行或者列的所有棋翻面即黑变白,白变黑。当棋盘上的棋形成某个形状的时候,便会触发杨有妹布好的魔法阵。魔法阵一旦被触发,就会将触发这个魔法阵的人吸入杨有妹的后宫。显然,杨有妹为了壮大实力,会去找很多人来玩这个游戏。杨有妹找了 $R$ 个男的或者女的来下棋,这 $R$ 个人每个人都会触发且仅触发 $N+M$ 个魔法中的一个 。由牛顿第四定律,杨有妹已经提前知道了每个人会触发哪个魔法,所以实际上会被吸入杨有妹后宫的人也是确定的。但是,杨有妹喜欢玩刺激的,所以杨有妹决定利用宇宙第零速度来改变未来。杨有妹可能会改掉某个人触发的魔法,还有可能将连续一段人所触发的魔法全部变成同一个。杨有妹想要知道,在他改变了未来的世界线之后,某一段人中究竟有多少人会被吸入他的后宫呢?为了简化你的任务,杨有妹做出以下规定:

1、一开始所有棋都是白色。

2、一开始所有人都只会触发编号为 $1$ 的魔法。

3、编号为 $1\sim N$ 的魔法对应 $N$ 行,编号为 $M+1$ 到 $N+M$ 的魔法对应 $M$ 列。

(每次个人会改变一个棋盘一行或者一列的状态,每次会修改每个人的操作,询问区间内会有多少个人触发法阵。)

输入格式

第一行两个整数 $N,M$ 代表棋盘大小。

接下来 $N$ 行每行 $M$ 个数,代表会触发魔法阵棋盘的形状。其中 $0$ 代表白色 $1$ 代表黑色。

接下来一行两个数 $R,Q$,代表总人数和杨有妹要搞事的次数。

接下来 $Q$ 行,每行第一个整数 $op$ 代表杨有妹要搞事的种类:

0、如果 $op=0$,则接下来两个整数 $x,y$,代表杨有妹把第 $x$ 个人触发的魔法改为了第 $y$ 个魔法。

1、如果 $op=1$,接下来两个整数 $l,r$,代表杨有妹想知道第 $l$ 个人到第 $r$ 个人中有多少个人会被吸入后宫。注意即使只询问这一段,在这一段之前的人也会触发魔法。

2、如果 $op=2$,接下来三个整数 $l,r,x$,代表杨有妹把第 $l$ 个人到第 $r$ 个人触发的魔法全部修改为了第 $x$ 种魔法。

输出格式

对于每次 $op=1$ 的搞事,输出一行代表搞事的结果。

样例输入

2 3
0 0 1
1 1 0
7 4
1 1 7
0 2 3
0 3 4
1 1 7

样例输入

0
3

数据规模与约定

测试点编号 $N$ $M$ $R$ $Q$
$1$ $1$ $1$ $50$ $100$
$2$ $1$ $2$ $100$ $200$
$3$ $2$ $2$ $2000$ $2000$
$4$ $2$ $2$ $130000$ $10000$
$5$ $2$ $3$ $130000$ $10000$
$6$ $2$ $3$ $130000$ $20000$
$7$ $2$ $3$ $130000$ $30000$
$8$ $2$ $3$ $250000$ $120000$
$9$ $2$ $3$ $500000$ $120000$
$10$ $2$ $3$ $500000$ $120000$

题解:

首先理解题意,一共 $N$ 行 $M$ 列,每一列有“被翻转奇数次”和“被翻转偶数次”两种状态。因此共 $2^{N+M}$ 种状态。

下称题目描述中的 $R$ 为 $n$。

而这 $2^{N+M}$ 种状态中,有 $0$ 种或 $2$ 种状态可以导致最终状态($0$ 种时为不合法状态,$2$ 种时两种状态在二进制下相反)。当 $2$ 种状态时,令它们分别为 $a_1,a_2$。

我们每次在 $op=1$ 的询问中就是要查询 $l$ 到 $r$ 之间有多少个数的异或前缀和为 $a_1$ 或 $a_2$。$op=0$ 和 $op=2$ 都当区间修改就好。

可以发现,当进行区间修改时,这一段区间中的前缀和会变为两个数交替出现;这一段后面会根据 $1$ 到 $r$ 的前缀和变化而变化,这一段前面不变。

即若原来 $sum_{1,r}=x$,修改后 $sum_{1,r}=y$,那么 $r+1$ 到 $n$ 位置上的这些数就都会异或上 $x\operatorname{xor}y$,记 $z=x\operatorname{xor}y$,后面会用到。

这样的话我们还需要维护区间修改区间查询的异或和,用一个线段树就可以搞定。

然后开 $2^{N+M}$ 棵平衡树,第 $i$ 棵平衡树维护前缀和为 $i$ 的元素的出现位置。其中 $\sum_{i=0}^{2^{N+M}-1}sz[root_i]=n$。

当 $[l,r]$ 区间修改为 $X$ 时,先把 $2^{N+M}$ 棵平衡树中的这一段删掉,然后在第 $sum_{1,l-1}\operatorname{xor}X$ 棵平衡树中插入 $\{l,l+2,\ldots,r-(r-l\mod2)\}$;在第 $sum_{1,l-1}$ 棵平衡树中插入 $\{l+1,l+3,\ldots,r-(r-l+1\mod 2)\}$。然后把第 $i$ 棵平衡树中的 $r+1$ 到 $n$ 部分和 $i\operatorname{xor}z$ 交换,说明后面的值全部异或上了 $z$。

我们发现这时会在同一棵平衡树中插入很多 $\{l+2k,k\in\mathbb Z,l\le k\le t\}$,此时把平衡树分裂合并稍微修改一下就可以实现。

最终每次查询第 $a_1$ 棵树中在 $[l,r]$ 有多少个元素、第 $a_2$ 棵树中在 $[l,r]$ 有多少个元素,把它们加起来输出就可以了。

时间复杂度 $O(2^{N+M}Q\log n)$。

Code:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read()
{
    int x=0;
    char ch=gc();
    while(ch<'0'||ch>'9')
        ch=gc();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x;
}
namespace SGT
{
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((L+R)>>1)
int v[2000000],lazy[2000000];
void pushdown(int k,int L,int R)
{
    if(!lazy[k]||L==R)
        return;
    int x=lazy[k];
    lazy[k]=0;
    v[ls]=x*((mid-L+1)&1);
    lazy[ls]=x;
    v[rs]=x*((R-mid)&1);
    lazy[rs]=x;
}
void change(int k,int l,int r,int L,int R,int x)
{
    if(r<L||l>R)
        return;
    if(l<=L&&r>=R)
    {
        v[k]=x*((R-L+1)&1);
        lazy[k]=x;
        return;
    }
    pushdown(k,L,R);
    change(ls,l,r,L,mid,x);
    change(rs,l,r,mid+1,R,x);
    v[k]=v[ls]^v[rs];
}
int ask(int k,int l,int r,int L,int R)
{
    if(r<L||l>R)
        return 0;
    if(l<=L&&r>=R)
        return v[k];
    pushdown(k,L,R);
    return ask(ls,l,r,L,mid)^ask(rs,l,r,mid+1,R);
}
#undef ls
#undef rs
}
namespace BST
{
int root[1<<5],pcnt=0;
int v[10000000],le[10000000],ls[10000000],rs[10000000],sz[10000000],rdm[10000000];
int Newnode(int x,int l)
{
    v[++pcnt]=x;
    rdm[pcnt]=rand();
    le[pcnt]=l;
    sz[pcnt]=l;
    return pcnt;
}
void maintain(int k)
{
    sz[k]=sz[ls[k]]+le[k]+sz[rs[k]];
}
int Merge(int a,int b)
{
    if(!a||!b)
        return a|b;
    if(rdm[a]<rdm[b])
    {
        rs[a]=Merge(rs[a],b);
        maintain(a);
        return a;
    }
    ls[b]=Merge(a,ls[b]);
    maintain(b);
    return b;
}
void split(int rt,int k,int &a,int &b)
{
    if(!rt)
    {
        a=b=0;
        return;
    }
    if(k<v[rt])
    {
        b=rt;
        split(ls[rt],k,a,ls[b]);
    }
    else if(k<v[rt]+2*le[rt]-2)
    {
        a=rt;
        int tmp=(k-v[rt])/2+1;
        b=Newnode(v[rt]+2*tmp,le[a]-tmp);
        le[a]=tmp;
        rs[b]=rs[rt];
        rs[rt]=0;
        maintain(a);
        maintain(b);
    }
    else
    {
        a=rt;
        split(rs[rt],k,rs[a],b);
    }
    maintain(rt);
}
}
using SGT::change;
using SGT::ask;
using BST::root;
using BST::Merge;
using BST::split;
using BST::Newnode;
//SGT maintains the exact num
//BST maintains the xor sum
int c[5][5];
int a1=-1,a2=-1;
int N,M,n,m;
void modify(int l,int r,int x)
{
    int sum1=(l==1)?0:ask(1,1,l-1,1,n);
    int sum2=ask(1,1,r,1,n);
    int a,b,c,d;
    for(int i=0;i<(1<<(N+M));++i)
    {
        split(root[i],l-1,a,b);
        split(b,r,b,c);
        root[i]=Merge(a,c);
    }
    change(1,l,r,1,n,x);
    int sum3=sum1^(x*((r-l+1)&1));
    split(root[sum1],l-1,a,b);
    root[sum1]=Merge(Merge(a,Newnode(l+1,(r-l+1)>>1)),b);
    split(root[sum1^x],l-1,a,b);
    root[sum1^x]=Merge(Merge(a,Newnode(l,(r-l+2)>>1)),b);
    int y=sum2^sum3;
    for(int i=0;i<(1<<(N+M));++i)   
        if((i^y)>i)
        {
            split(root[i],r,a,b);
            split(root[i^y],r,c,d);
            root[i]=Merge(a,d);
            root[i^y]=Merge(c,b);
        }
}
int main()
{
    #ifdef wjyyy
        freopen("a.in","r",stdin);
    #endif
    N=read();
    M=read();
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            c[i][j]=read();
    for(int i=0;i<(1<<(N+M));++i)
    {
        int C[5][5];
        memset(C,0,sizeof(C));
        int t=i;
        for(int j=1;j<=N;++j)
        {
            if(t&1)
                for(int I=1;I<=M;++I)
                    C[j][I]^=1;
            t>>=1;
        }
        for(int j=1;j<=M;++j)
        {
            if(t&1)
                for(int I=1;I<=N;++I)
                    C[I][j]^=1;
            t>>=1;
        }
        int flag=0;
        for(int j=1;j<=N;++j)
            for(int k=1;k<=M;++k)
                if(C[j][k]!=c[j][k])
                    flag=1;
        if(!flag)
        {
            if(~a1)
                a2=i;
            else
                a1=i;
        }
    }
    n=read();
    m=read();
    change(1,1,n,1,n,1);
    root[1]=Newnode(1,(n+1)>>1);
    root[0]=Newnode(2,n>>1);
    int op,u,v,w,a,b,c;
    for(int i=1;i<=m;++i)
    {
        op=read();
        if(op==0)
        {
            u=read();
            v=read();
            modify(u,u,1<<(v-1));
        }
        else if(op==1)
        {
            u=read();
            v=read();
            if(a1==a2)
            {
                split(root[a1],u-1,a,b);
                split(b,v,b,c);
                printf("%d\n",BST::sz[b]);
                root[a1]=Merge(Merge(a,b),c);
            }
            else
            {
                int ans=0;
                split(root[a1],u-1,a,b);
                split(b,v,b,c);
                ans+=BST::sz[b];
                root[a1]=Merge(Merge(a,b),c);
                split(root[a2],u-1,a,b);
                split(b,v,b,c);
                printf("%d\n",ans+BST::sz[b]);
                root[a2]=Merge(Merge(a,b),c);
            }
        }
        else
        {
            u=read();
            v=read();
            w=read();
            modify(u,v,1<<(w-1));
        }
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */