巧妙运用位运算

本文旨在通过两道巧妙运用位运算的题，认识位运算的魅力

题目一

题意：
给定两个序列\(A,B\)，求\(A,B\)的最长公共子序列
\(|A|,|B|\le 10^5\)
时限：\(5s\)

目前求任意两序列的最长公共子序列，是没有复杂度低于\(O(|A|\cdot |B|)\)的算法的

回顾经典的\(O(|A|\cdot |B|)\)

\[f_{i,j}=max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[A_i+B_j]) \]

显然有如下性质：

\[\begin{aligned} &f_{i,j-1}\le f_{i,j}\\ &f_{i-1,j-1}\le f_{i,j}\\ &f_{i,j}-f_{i,j-1}\le 1\\ &f_{i,j}-f_{i-1,j}\le 1 \end{aligned}\]

令\(M_{i,j}=f_{i,j}-f_{i,j-1}\)
考虑转移
我们将\(\text{M}_{i-1}\)划分为若干段，每段以一个\(1\)结尾：

[000...01][000...01][000...0]
 ^^                        ^
 12                       |B|

考虑\(A_i\)出现在\(B\)中的位置集合，令其为\(\text{Ab}\)
令\(\text{X=M}_{i-1}|\text{Ab}\)
对于\(\text{M}_{i-1}\)的每一段，保留\(\text{X}\)最前面的一个\(1\)，则为\(\text{M}_i\)

例如

$M_{i-1}$=[000...01][000...01][000...0]
     $Ab$=[110...00][000...00][001...0]
    $M_i$=[100...00][000...01][001...0]

我们已知了转移方式，考虑如何通过位运算得到

对于某一段如：X=[0011001]
考虑前导0变成1，第一个1变成0：[1101001]
异或上X，得到[1110000]
在按位与上X，得到[0010000]

我们将\(\text{X}\)翻转，第一步操作变成

X=[1001100]
  [1001011]

这个意义是\(-1\)，这是一段的操作，对所有段如何快速进行呢
发现我们将\(\text{M}_{i-1}\)整体翻转后
再左移，给最右边填上\(1\)，效果为：

$M_{i-1}$=[000...0][100...0][100...0]
           ^                      ^^
          |B|                     21
          [000...1][000...1][000...1]
这恰好使得每一段都变成1

那么直接减即可，具体细节见代码
将矩阵的行压成\(K\)块，即可实现\(O(|A|\cdot K)\)的时间复杂度
以下代码在\(n,m=10^5\)，不开任何优化的情况下，跑进1s

#include<bits/stdc++.h>
typedef int LL;
typedef unsigned long long ull;
const LL maxn=1e5+9;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1; c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();
	}return x*f;
}
LL n,m,ans;
LL a[maxn],b[maxn];
ull dp[maxn/63],pos[maxn][maxn/63];
int main(){
	n=Read(); m=Read();
	for(LL i=0;i<n;++i){
		a[i]=Read();
	}
	for(LL i=0;i<m;++i){
		b[i]=Read();
	}
	for(LL i=0;i<m;++i){
		pos[b[i]][i/63]|=1ull<<i%63;
	}
	LL up=(m-1)/63;
	for(LL i=0;i<n;++i){
		LL x(a[i]);
		ull pre(1ull<<63);
		for(LL j=0;j<=up;++j){
			ull a(dp[j]),c(a|pos[x][j]|1ull<<63);
			ull tmp(((c-(a<<1ull|1))^c)&c);
			if(pre<(1ull<<63)){
				tmp-=tmp&(-tmp);
			}
			pre=tmp;
			dp[j]=tmp&((1ull<<63)-1);
		}
		if(pre<(1ull<<63)) ++ans;
	}
	printf("%d\n",ans);
}

题目二

题意
给定\(n\)个点，第\(i\)个点为\((i,p_i)\)（序列\(\{p_i\}\)为\(\{1,2,\cdots,n\}\)的某个排列）
每个点还有一个颜色\(c_i\)
\(q\)次询问，每次给定\(l,r,d,u\)，求集合\(\{i|i\in[l,r],p_i\in[d,u]\}\)的颜色个数
\(n,q\le 10^5\)

令\(A_{c,i}\)为第\(i\)次询问是否包含颜色\(c\)，考虑得到其

显然可以将\(i\in[l,r],p_i\in[d,u]\)可以拆开
令\(X_{i,j}\)为第\(j\)次询问是否满足\(l_j\le i\le r_j\)，我们对于\((l_j,j)(r_j+1,j)\)进行扫描线，能很轻松的得到
令\(Y_{i,j}\)为第\(j\)次询问是否满足\(d_j\le i\le u_j\)，同理可得
那么\((X_i\And Y_j)_j\)即为点\(i\)是否被包含在第\(j\)次询问中
现在可以很简单得到\(A\)

矩阵\(A\)显然为01矩阵，需要将各行按列相加，得到答案
对于每列，这里我们如此维护其答案：

令\(cnt_i\)为第\(i\)列目前的答案
\(cnt_i=\sum\limits_{k=0}^{\infty} 2^k\cdot C_{k,i}\)（其中\(C\)为01矩阵）
假设这里\(cnt_i\le N\)，那么改写成
\(cnt_i=\sum\limits_{k=0}^{logN} 2^k\cdot C_{k,i}\)
令\(logN\)为矩阵的行数，称为\(h\)

那么我们分治，对于颜色\(\in[l,mid]\)，令其矩阵为\(C_0\)，对于颜色\(\in(mid,r]\)，令其矩阵为\(C_1\)
考虑合并\(C_0,C_1\)：\(C'=C_0+C_1\)，假设\(C_0,C_1\)的\(h_0,h_1\)均为\(l\)，为了方便，则矩阵\(C\)的\(h=l+1\)
合并的过程，相当于是二进制高精，考虑进位，很容易实现

分析其时间复杂度
令颜色种类为\(N\)，令\(K\)为将矩阵\(C\)的行压成的块数
\(T(N)=2T(N/2)+KlogN\)，\(K\)为常数，提取出来
\(T(N)=2T(N/2)+logN\)，运用主定理得到\(T(N)=N\)
时间复杂度为\(O(K\cdot N)\)

巧妙运用位运算

题目一

题目二

推荐阅读