黑白棋 题解【平衡树】【线段树】【前缀和】
点击量：229
数据结构好题。学会了平衡树代替权值线段树（雾
题目描述
黑白棋的棋盘有 $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;
}
说点什么