正題
題目連結:https://loj.ac/p/6564
題目大意
給兩個序列\(a,b\)求它們的最長公共子序列。
\(1\leq n,m,a_i,b_i\leq 7\times 10^4\)
解題思路
無意間看到的一個\(bitset\)科技。
首先設\(f_{i,j}\)表示\(a\)串比對到第\(i\)個\(b\)串比對到第\(j\)個時的最長長度，做過\(dp\)套\(dp\)的應該知道\(f_{i,j}\)的性質。
\[0\leq f_{i,j}-f_{i,j-1}\leq 1
\]
基本的思路就是設\(01\)矩陣\(M\)滿足\(f_{i,j}=\sum_{k=1}^jM_{i,k}\)然後用\(bitset\)優化轉移
然後考慮一下怎麼轉移，我們先預處理出\(p\)數組其中\(p_i\)表示數字\(i\)出現的位置集合
我們的轉移要把\(M\)中的\(1\)盡量的往前移動并且看能否加上一個新的\(1\)。
假設現在的字元是\(c\)，那麼我們将使用\(p_c\)進行轉移。
我們把\(M\)中每個\(1\)作為結尾分成若幹段（最後的\(0\)也是一段，順序是從低位到高位）。
那麼對于一段中如果這一段\(p_c\)有\(1\)那麼我們就取最前面的那個\(1\)，這樣因為前面假設有\(j\)個\(1\)那麼這次就比對\(p_c\)最前面的那個作為\(j+1\)。
但是我們顯然不可能一段一段做，我們可以考慮怎麼把這個操作轉成位運算🤔。
考慮一下我們平時是怎麼取一個\(01\)串的第一位的，我們有\(lowbit(x)=((x-1)\ xor\ x)\ and\ x\)對吧。
發現這裡每段分開取實際上難實作的地方隻有\(x-1\)，考慮怎麼實作這個問題。
因為\(1\)是段的末尾，是以每一段的開頭前面都是\(1\)，是以如果我們讓\(M\)左移一位那麼就變成開頭是\(1\)了（需要注意補上第一段的\(1\)，是以應該是\((M<<1)+1\)）
最後來說是
\[M=(X-(M<<1)+1)\ xor\ X\ and\ X
這樣我們就完成了\(M\)的轉移，因為需要位運算，是以需要手寫\(bitset\)。
時間複雜度\(O(\frac{nm}{\omega})\)
我是看這篇部落格學的，看不懂的可以去看下:https://www.cnblogs.com/-Wallace-/p/bit-lcs.html
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ull unsigned long long
using namespace std;
const int N=7e4+10;
int n,m,L;
struct bitset{
ull t[N/64+5];
bitset(){memset(t,0,sizeof(t));return;}
void set(int p){
t[p>>6]|=(1ull<<(p&63));
return;
}
void shift(){
ull last=0;
for(int i=0;i<L;i++){
ull cur=t[i]>>63;
(t[i]<<=1)|=last;
last=cur;
}
return;
}
int count(){
int ans=0;
for(int i=0;i<L;i++)
{ull x=t[i];while(x)x-=(x&-x),ans++;}
return ans;
}
bitset& operator=(const bitset &b)
{memcpy(t,b.t,sizeof(t));return *this;}
bitset& operator|=(const bitset &b){
for(int i=0;i<L;i++)t[i]|=b.t[i];
return *this;
}
bitset& operator&=(const bitset &b){
for(int i=0;i<L;i++)t[i]&=b.t[i];
return *this;
}
bitset& operator^=(const bitset &b){
for(int i=0;i<L;i++)t[i]^=b.t[i];
return *this;
}
}p[N],f,g;
bitset operator-(const bitset &a,const bitset &b){
bitset tmp;ull last=0;
for(int i=0;i<L;i++){
ull cur=(a.t[i]<b.t[i]+last);
tmp.t[i]=a.t[i]-b.t[i]-last;
last=cur;
}
return tmp;
}
int main()
{
scanf("%d%d",&n,&m);L=(n>>6)+1;
for(int i=1,c;i<=n;i++)
scanf("%d",&c),p[c].set(i);
for(int i=1,c;i<=m;i++){
scanf("%d",&c);
(g=f)|=p[c];
f.shift();f.set(0);
f=g-f;f^=g;f&=g;
}
printf("%d",f.count());
return 0;
}