题解 P4428 【[BJOI2018]二进制】

传说中的动态dp？反正极其毒瘤就是了 如果足够熟练的话应该可以轻松的通过本题，但是不熟练的话就需要肝一段时间了…… # 本题题解 首先让我们先来推一发结论…… 题目中的意思是存在一种重排方案使得这个序列是3的倍数就计入答案当中 通过打表发现，2的奇数次方%3=2,2的偶数次方%3=1(根据费马小定理$2^2\%3=1$所以次幂一定循环) 对于重排的二进制数膜3我们可以认为是每一二进制位膜三之后加起来再膜3的结果 所以我们如果将这个二进制数的每一位%3，就会得到一堆余数，我们的目标是构造一种方案使得这个区间重排之后这些余数的和%3为0 因此我们大概需要一个类似于判定定理之类的东西来让我们快速的判定这个区间重新排列之后是否可以成为3的倍数 发现如果这个区间有偶数个1那么一定可以重新排列成3的倍数，因为我们可以在这个区间的所有奇数位上放置一半的1，所有偶数位置上放置另一半的1，然后1和2两两配对就可以凑出整数个3，因此%3=0 所以现在让我们把精力集中在这个区间存在着奇数个1的情况，发现我们如果这个区间有3个及以上的1的话，我们可以让奇数位置比偶数位置多3个3，此时大部分的1是1+2=3两两配对成3了，最后的3个2刚好凑成一个6，也可以被3整除，可以证明就算存在其他形式的构造方法，这种构造方式也一定可以构造出一个解，但是如果连这种构造方式都无解的话，其他的构造形式一定构造不出解来 但是我们发现这样会有一个非常致命的问题，我们的奇数位置至少要比偶数位置多3个才能完成构造 于是我们发现奇数个1+3个0的情况是可以构造成功的，奇数个1+2个0的情况依然可以构造成功(此时序列有奇数个元素，奇数位置本身就比偶数位置多一个，加上2个0刚好差出3个位置) 但是奇数个1+1个0的情况一定不行，因为此时序列之和已经%3=0，无论最后的0放在什么位置上都会使%3的结果变成非0 当然奇数个1+0个0的情况因为重排都是一个样所以没法构造了 简单分析下刚才的情况，我们发现一个区间可以被重排成3的倍数的条件相当繁琐，但是我们发现判断一个区间不可以被重排成3的倍数的判断条件相对简单，只需要满足下列三个条件中至少一个 1.有且仅有1个1 2.有奇数个1且有1个0 3.有奇数个1且有0个0 我们发现如果只是询问一次的话似乎可以dp求出来这个区间有多少个点对不符合条件,大概开上3维表示这个区间有没有1,1的奇偶性，0的数量，然后就可以大力转移了 此时我们发现有$10^5$组询问和修改我们是铁定凉凉的，此时有必要介绍一种被称之为动态dp的黑科技了…… ## 动态dp 所谓动态dp就是带修改的dp 我们发现有些dp是一个点一个点更新的，这样做太慢了，我们有必要给它提个速 于是我们决定把这个dp搬到线段树上，然后我们就可以支持单点询问和区间修改了 如果你真的足够毒瘤的话可以链剖之后在树上以链分治的形式做dp，把dp搬到链剖之后的线段树上……这就已经不是毒瘤可以做出来的事情了当然这道题还是非常亲民的序列上的动态dp 那么我们具体来讲如何把dp搬到线段树上吧，我们都知道线段树的每一个节点代表着一个区间，因此我们可以在这个区间里做dp，实现方法如下 对于线段树的每一个节点，我们维护一个dp数组 ## $Dp_{i,j,k,p}$ 其中i的意义如下所示 $i=0$这个区间不包含该节点的左端点和右端点 $i=1$这个区间包含该节点的左端点，不包含右端点 $i=2$这个区间不包含该节点的左端点，包含右端点 $i=3$这个区间是该节点对应的区间(或者说既包含左端点又包含右端点) j的意义表示这个区间有奇数个1或偶数个1，1表示奇数，0表示偶数 k的意义表是这个区间有0个1或者1个1 p的意义表示这个区间有0个0或者1个0 $Dp_{i,j,k,p}$的值表示满足$i,j,k,p$约束的区间有多少个 然后我们发现转移方程写起来将会十分蛋疼……基本不可写…… 不可写就算了(参见\[六省联考2017摧毁树状图]),问题是我们冷静分析下这个数组的长度$4*2*2*2=32$常数大到天上去了基本过不掉，更别说你线段树还有2的基础常数…… 因此我们需要尽量减少这个数组的长度，只要略微少点就行了 发现只有一个1的区间似乎和其他两个限制条件没啥关系，因此可以单独dp 所以我们发现可以把一棵线段树拆成两个线段树，分别dp 第一个线段树上存这样的dp数组 ## $Dp_{i,j,k}$ 其中i的定义和一开始的定义一样 j表示这个区间有奇数个1或者偶数个1 k表示这个区间有0个0或1个0 另一个线段树存这样的dp数组 ## $Dp_{i,j}$ i的定义还是和开始的定义一样， j表示这个区间有0个1或者1个1 然后我们再算一下dp数组的长度，会发现长度变成了 $4*2*2+4*2=26$常数减少了8不说，而且转移方程变好写了，基本在人写的代码和$Data Structure Master$写的代码难度之间了 然后让我们来推这个线段树上dp的转移方程好了 普通dp的式子是加一个点然后递推，而线段树上的式子就是merge左右两个儿子，然后dp 那么我们因为转移方程太过鬼畜了，我们可以分维考虑，考虑每一个dp维度转移时发生的变化 方便起见，我们设父亲节点为$p$，左儿子节点为$p1$，右儿子节点为$p2$ 先考虑几个比较简单的转移 奇数个1+奇数个1=偶数个1 奇数个1+偶数个1=奇数个1 0个0+1个0=1个0 0个0+0个0=0个0 0个1+0个1=0个1 1个1+0个1=1个1 然后考虑非常复杂的i这一维的转移，看不懂的话自己画图吧 先解释一下，下面说的加法转移就是继承儿子里已有的区间，乘法转移就是两个儿子中的区间拼接成的区间 p的0型区间： 加法转移:儿子的0型区间以及p1的2型区间，p2的1型区间 乘法转移:p1的2型区间拼上一个p2的1型区间 p的1型区间： 加法转移:p1的3型区间以及p1的1型区间 乘法转移:p1的3型区间拼上p2的1型区间 p的2型区间 加法转移:p1的3型区间以及p2的2型区间 乘法转移:p1的2型区间拼上p2的3型区间 p的3型区间 加法转移:?不存在的！ 乘法转移：p1的3型区间以及p2的3型区间 有了这些毒瘤的转移规则我们可以写出一个线段树的merge函数(有的人叫pushup或者update)，然后我们此时就可以完成单点修改和建树工作了……就是简单的一路merge上去应该就是普通线段树操作，应该还是非常好写的 问题是如何完成区间查询操作? 我们可以把0号点当成一个空区间，在线段树上跑区间拆分函数，如果当前区间和节点对应的区间是否重合，如果重合的话我们判断一下0号节点是否为空，如果为空的话就将这个节点的dp数组复制给0号节点，否则将0号节点的dp数组复制一份给4n+1号节点，然后merge(0,4n+1,p)即可，这样我们就一个一个的把这些区间merge成了一个区间，并存在了0号节点里 最后我们只需要提取0号节点的dp数组就是这个区间对应的dp数组了 做完了？ # 不，你重复计数了！ 我们观察仅有1个1的区间既是“有且仅有一个1的区间”，也是"有奇数个1且有0个0的区间"，形如"10,01"的区间既是“有且仅有1个1的区间”，也是“有奇数个1且有1个0的区间”，因此这两个区间都被算了两边……问题开始变得辣手…… 莫非我们要修改我们的算法，使他变得更加简单，更加优雅，更加具有一般性？ # 不，直接加上重复减的情况就行了 仅有一个1的区间就是区间中1的个数，直接使用树状数组就可以维护，形如“01,10”的区间的话，我们可以每个点记一个0/1的值，表示他和后一个点是否构成了形如"01,10"的区间，然后还是树状数组查一发区间和即可维护 修改的时候同时在两个线段树和两个树状数组上各改一遍 听起来这个算法的常数该大到天上去了，但是事实上跑的飞起，吸氧之后最慢的的点就跑了238ms…… 然后看一看恶心至极的实现吧……，我写了150行，极其恶心就是了 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10;typedef long long ll; int n;int a[N];int mk;int m; struct linetree1//这个线段树维护条件2,3 { ll v[4*N][4][2][2]; inline void merge(int p,int p1,int p2)//非常恶心的merge函数 { for(int i=0;i<=1;i++)for(int k=0;k<=1;k++)//加法转移们 v[p][0][i][k]=v[p1][0][i][k]+v[p2][0][i][k]+v[p1][2][i][k]+v[p2][1][i][k]; for(int i=0;i<=1;i++)for(int k=0;k<=1;k++)v[p][1][i][k]=v[p1][3][i][k]+v[p1][1][i][k]; for(int i=0;i<=1;i++)for(int k=0;k<=1;k++)v[p][2][i][k]=v[p2][3][i][k]+v[p2][2][i][k]; for(int i=0;i<=1;i++)for(int k=0;k<=1;k++)v[p][3][i][k]=0; for(int i=0;i<=1;i++)//乘法转移,这里for枚举p1,p2各选多少个0 for(int j=0;i+j<=1;j++)//手动枚举了奇偶性的转移 v[p][0][0][i+j]+=v[p1][2][0][i]*v[p2][1][0][j]+v[p1][2][1][i]*v[p2][1][1][j], v[p][0][1][i+j]+=v[p1][2][0][i]*v[p2][1][1][j]+v[p1][2][1][i]*v[p2][1][0][j], v[p][1][0][i+j]+=v[p1][3][0][i]*v[p2][1][0][j]+v[p1][3][1][i]*v[p2][1][1][j], v[p][1][1][i+j]+=v[p1][3][0][i]*v[p2][1][1][j]+v[p1][3][1][i]*v[p2][1][0][j], v[p][2][0][i+j]+=v[p1][2][0][i]*v[p2][3][0][j]+v[p1][2][1][i]*v[p2][3][1][j], v[p][2][1][i+j]+=v[p1][2][0][i]*v[p2][3][1][j]+v[p1][2][1][i]*v[p2][3][0][j], v[p][3][0][i+j]+=v[p1][3][0][i]*v[p2][3][0][j]+v[p1][3][1][i]*v[p2][3][1][j], v[p][3][1][i+j]+=v[p1][3][0][i]*v[p2][3][1][j]+v[p1][3][1][i]*v[p2][3][0][j]; } inline void modify(int p,int l,int r,int pos)//和一般的线段树修改并没什么区别 { if(r-l==1)//注意一开始只有3型区间有值 { if(a[r]){v[p][3][1][0]=1;v[p][3][0][1]=0;} else {v[p][3][0][1]=1;v[p][3][1][0]=0;}return; }int mid=(l+r)/2;//判断向左向右走 if(pos<=mid){modify(p<<1,l,mid,pos);}else {modify(p<<1|1,mid,r,pos);} merge(p,p<<1,p<<1|1);//merge一下 } inline void query(int p,int l,int r,int dl,int dr)//拆分成log个区间然后从左至右顺次合并 { if(dl==l&&dr==r) { if(mk==0)//空区间直接复制 { for(int i=0;i<=3;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)v[0][i][j][k]=v[p][i][j][k];mk=1; }else//否则复制一份给4n+1然后相当于merge自己和p { for(int i=0;i<=3;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)v[4*n+1][i][j][k]=v[0][i][j][k]; merge(0,4*n+1,p); }return; }int mid=(l+r)/2;//区间拆分 if(dl<mid){query(p<<1,l,mid,dl,min(dr,mid));} if(mid<dr){query(p<<1|1,mid,r,max(dl,mid),dr);} } inline ll cquery(int l,int r) { for(int i=0;i<=3;i++)//记得清空0号节点 for(int j=0;j<=1;j++) for(int k=0;k<=1;k++)v[0][i][j][k]=0;mk=0; query(1,0,n,l,r);ll ret=0;//统计奇数个1有0或1个0的区间数 for(int i=0;i<=3;i++)ret+=v[0][i][1][0]+v[0][i][1][1]; return ret; } inline void build(int p,int l,int r)//建树无脑merge就行了 { if(r-l==1){if(a[r]){v[p][3][1][0]=1;}else {v[p][3][0][1]=1;}return;} int mid=(l+r)/2;build(p<<1,l,mid);build(p<<1|1,mid,r);merge(p,p<<1,p<<1|1); } }lt1; struct linetree2//第二棵线段树单独维护条件2,和第一个树写法差不多 { ll v[4*N][4][2]; inline void merge(int p,int p1,int p2)//merge会比第一个树好写点 { for(int i=0;i<=1;i++)v[p][0][i]=v[p1][0][i]+v[p2][0][i]+v[p1][2][i]+v[p2][1][i]; for(int i=0;i<=1;i++)v[p][1][i]=v[p1][3][i]+v[p1][1][i]; for(int i=0;i<=1;i++)v[p][2][i]=v[p2][3][i]+v[p2][2][i]; for(int i=0;i<=1;i++)v[p][3][i]=0; for(int i=0;i<=1;i++) for(int j=0;i+j<=1;j++) v[p][0][i+j]+=v[p1][2][i]*v[p2][1][j], v[p][1][i+j]+=v[p1][3][i]*v[p2][1][j], v[p][2][i+j]+=v[p1][2][i]*v[p2][3][j], v[p][3][i+j]+=v[p1][3][i]*v[p2][3][j]; } inline void modify(int p,int l,int r,int pos)//其他的函数基本一样了 { if(r-l==1) { if(a[r]){v[p][3][1]=1;v[p][3][0]=0;} else {v[p][3][0]=1;v[p][3][1]=0;}return; }int mid=(l+r)/2; if(pos<=mid){modify(p<<1,l,mid,pos);}else {modify(p<<1|1,mid,r,pos);} merge(p,p<<1,p<<1|1);return; } inline void query(int p,int l,int r,int dl,int dr) { if(dl==l&&dr==r) { if(mk==0){for(int i=0;i<=3;i++)for(int j=0;j<=1;j++)v[0][i][j]=v[p][i][j];mk=1;} else { for(int i=0;i<=3;i++)for(int j=0;j<=1;j++)v[4*n+1][i][j]=v[0][i][j]; merge(0,4*n+1,p); }return; }int mid=(l+r)/2; if(dl<mid){query(p<<1,l,mid,dl,min(dr,mid));} if(mid<dr){query(p<<1|1,mid,r,max(dl,mid),dr);} } inline ll cquery(int l,int r) { for(int i=0;i<=3;i++)for(int j=0;j<=1;j++)v[0][i][j]=0;mk=0; query(1,0,n,l,r);ll ret=0; for(int i=0;i<=3;i++)ret+=v[0][i][1]; return ret; } inline void build(int p,int l,int r) { if(r-l==1){if(a[r]){v[p][3][1]=1;}else {v[p][3][0]=1;}return;} int mid=(l+r)/2;build(p<<1,l,mid);build(p<<1|1,mid,r);merge(p,p<<1,p<<1|1); } }lt2; struct treearray//树状数组维护需要特判的区间,这里封装了下 { int ta[N]; inline void c(int x,int t){for(;x<=n;x+=x&(-x)){ta[x]+=t;}} inline int d(int x){int r=0;for(;x>0;x-=x&(-x)){r+=ta[x];}return r;} inline ll q(int l,int r){return d(r)-d(l);} }tr1,tr2; int main() { scanf("%d",&n); for(int i=1;i<=n;i++){scanf("%d",&a[i]);}lt1.build(1,0,n);lt2.build(1,0,n);//建树,建树状数组 for(int i=1;i<=n;i++){if(a[i]){tr1.c(i,1);}if(a[i]^a[i+1]&&i!=n){tr2.c(i,1);}} scanf("%d",&m); for(int i=1,t,l,r;i<=m;i++) { scanf("%d",&t); if(t==1)//然后在每一个数据结构上修改就行了 { scanf("%d",&l);a[l]^=1; lt1.modify(1,0,n,l);lt2.modify(1,0,n,l);tr1.c(l,(a[l])?1:-1); if(l!=n){tr2.c(l,(a[l]^a[l+1])?1:-1);} if(l!=1){tr2.c(l-1,(a[l-1]^a[l])?1:-1);} } else { scanf("%d%d",&l,&r);ll len=r-l+1;//最后加上要特判的区间就行,注意边界条件,10,01的左端点只能到r-1 printf("%lld\n",len*(len+1)/2-lt1.cquery(l-1,r)-lt2.cquery(l-1,r)+tr1.q(l-1,r)+tr2.q(l-1,r-1)); } }return 0;//拜拜程序~ } ```