Description
给你两个串，求他们的最长公共上升子序列
Input
第一行是第一个串的长度\(n\)
第二行\(n\)个数代表第一个串
第三行是第二个串的长度\(m\)
第四行\(m\)个数代表第二个串
Output
输出最长子序列的长度以及方案
Hint
\(For~All:\)
\(0~\leq~n~\leq~500\)
Solutoin
先考虑朴素DP，可以设\(f_{i,j}\)代表第一个串选前\(i\)个，第二个串选前\(j\)个的答案，转移显然\(f_{i,j}=\max\{f_{k,h}\}+1\),其中\(k~<~i,j~<~h,A_i=B_j,A_k=B_h\)。复杂度为\(O(n^4)\)，GG。
考虑把这个问题放到一个串上，问题变成了求一个串的LIS，我口胡了一个十分鬼畜的算法：读入离散化以后，设\(f_i\)为当前算到的以\(i\)这个数结尾的ans，注意这里\(i\)是代表的是一个位置的值而不是下标。于是当正着扫描的时候，转移显然\(f_i=\max\{f_j\}+1\)，其中\(j~<~i\)。发现\(f_i\)是从\(f_j\)的前缀\(\max\)转移过来的。于是可以使用树状数组维护这个前缀\(\max\)。具体的，\(f_i=ask(i-1)+1\)，然后在树状数组上修改\(i\)位置的\(f_i\)。
考虑一共枚举\(n\)个位置，树状数组复杂度是\(O(logn)\)，总复杂度为\(O(nlogn)\)
在这里放上一个串的树状数组LIS代码
#include#include #include #define rg register#define ci const int#define cl const long long inttypedef long long int ll;namespace IO { char buf[300];}template inline void qr(T &x) { rg char ch=getchar(),lst=' '; while((ch > '9') || (ch < '0')) lst=ch,ch=getchar(); while((ch >= '0') && (ch <= '9')) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); if(lst == '-') x=-x;}template inline void qw(T x,const char aft,const bool pt) { if(x < 0) {putchar('-');x=-x;} rg int top=0; do { IO::buf[++top]=x%10+'0'; } while(x/=10); while(top) putchar(IO::buf[top--]); if(pt) putchar(aft);}template inline T mmax(const T a,const T b) {return a > b ? a : b;}template inline T mmin(const T a,const T b) {return a < b ? a : b;}template inline T mabs(const T a) {return a < 0 ? -a : a;}template inline void mswap(T &a,T &b) { T _temp=a;a=b;b=_temp;}const int maxn = 100010;int n;int MU[maxn],tree[maxn],frog[maxn],temp[maxn];int ask(int);void init_hash();void change(int,ci);inline int lowbit(ci x) {return x&(-x);}int main() { qr(n); for(rg int i=1;i<=n;++i) {qr(MU[i]);temp[i]=MU[i];} init_hash(); for(rg int i=1;i<=n;++i) { frog[MU[i]]=ask(MU[i]-1)+1; change(MU[i],frog[MU[i]]); } qw(n-ask(n),'\n',true); return 0;}void init_hash() { std::sort(temp+1,temp+1+n); int *ed=std::unique(temp+1,temp+1+n); for(rg int i=1;i<=n;++i) MU[i]=std::lower_bound(temp+1,ed,MU[i])-temp;}int ask(int x) { int _ans=0; while(x) { _ans=mmax(_ans,tree[x]); x-=lowbit(x); } return _ans;}void change(int x,ci v) { while(x <= n) { tree[x]=mmax(tree[x],v); x+=lowbit(x); }}
回到这个题，我们可以仿照一个串的方式，再加一个维度，设\(f_{i,j}\)第一个串算到当前以\(i\)这个数结尾，第二个串以第\(j\)个位置结尾的\(ans\)。注意这里\(i\)代表的A串的值，\(j\)代表的是\(b\)串的下标。于是转移显然\(f_{i,j}=\max\{f_{k,h}\}+1\)，其中\(k~<~i,h<j\)。于是发现\(i,j\)由一个矩形的前缀最大值转移过来，可以用二维树状数组维护这个最大值。这样复杂度降为\(O(n^2log^2n)\)，可以通过本题。
这里的一个姿势是二维树状数组，他可以维护一个矩形的二维前缀和或前缀最大值。查询代码为
Zay ask(ci x,ci y) { rg Zay _ret; for(rg int i=x;i;i-=lowbit(i)) { for(rg int j=y;j;j-=lowbit(j)) { _ret=mmax(_ret,tree[i][j]); } } return _ret;} 修改代码为
void add(ci x,ci y) { Zay _tp=Zay(x,y); for(rg int i=x;i<=tcnt;i+=lowbit(i)) { for(rg int j=y;j<=tcnt;j+=lowbit(j)) { tree[i][j]=mmax(tree[i][j],_tp); } }} 更一般的，修改代码中_tp可以改为一个传进来的参数代表要修改位置的值。
于是这个题就完了。
Code
#include#include #include #define rg register#define ci const int#define cl const long long inttypedef long long int ll;namespace IO { char buf[300];}template inline void qr(T &x) { rg char ch=getchar(),lst=' '; while((ch > '9') || (ch < '0')) lst=ch,ch=getchar(); while((ch >= '0') && (ch <= '9')) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); if(lst == '-') x=-x;}template inline void qw(T x,const char aft,const bool pt) { if(x < 0) {putchar('-');x=-x;} rg int top=0; do { IO::buf[++top]=x%10+'0'; } while(x/=10); while(top) putchar(IO::buf[top--]); if(pt) putchar(aft);}template inline T mmax(const T &a,const T &b) {return a > b ? a : b;}template inline T mmin(const T a,const T b) {return a < b ? a : b;}template inline T mabs(const T a) {return a < 0 ? -a : a;}template inline void mswap(T &a,T &b) { T _temp=a;a=b;b=_temp;}const int maxn = 1010;const int maxd = 1010;int n,m,tcnt;int a[maxn],b[maxn],MU[maxd],frog[maxd][maxd],remap[maxd];struct Zay { int x,y; inline bool operator<(const Zay &_others) const { return frog[this->x][this->y] < frog[_others.x][_others.y]; } inline bool operator>(const Zay &_others) const { return frog[this->x][this->y] > frog[_others.x][_others.y]; } Zay (ci _a=0,ci _b=0) {x=_a,y=_b;}};Zay tree[maxd][maxd],pre[maxn][maxn],ans;Zay ask(ci,ci);void init_hash();void add(ci,ci);void dfs(ci,ci);inline int lowbit(ci x) {return x&(-x);}int main() { qr(n); for(rg int i=1;i<=n;++i) {qr(a[i]);MU[++tcnt]=a[i];} qr(m); for(rg int i=1;i<=m;++i) {qr(b[i]);MU[++tcnt]=b[i];} init_hash(); for(rg int i=1;i<=n;++i) { for(rg int j=1;j<=m;++j) if(a[i] == b[j]) { Zay _temp=ask(a[i]-1,j-1); frog[a[i]][j]=frog[_temp.x][_temp.y]+1; pre[a[i]][j]=_temp; add(a[i],j); ans=mmax(ans,(Zay){a[i],j}); } } qw(frog[ans.x][ans.y],'\n',true); dfs(ans.x,ans.y); return 0;}void init_hash() { std::sort(MU+1,MU+1+tcnt); int *ed=std::unique(MU+1,MU+1+tcnt); rg int k; for(rg int i=1;i<=n;++i) k=std::lower_bound(MU+1,ed,a[i])-MU,remap[k]=a[i],a[i]=k; for(rg int i=1;i<=m;++i) k=std::lower_bound(MU+1,ed,b[i])-MU,remap[k]=b[i],b[i]=k;}Zay ask(ci x,ci y) { rg Zay _ret; for(rg int i=x;i;i-=lowbit(i)) { for(rg int j=y;j;j-=lowbit(j)) { _ret=mmax(_ret,tree[i][j]); } } return _ret;}void add(ci x,ci y) { Zay _tp=Zay(x,y); for(rg int i=x;i<=tcnt;i+=lowbit(i)) { for(rg int j=y;j<=tcnt;j+=lowbit(j)) { tree[i][j]=mmax(tree[i][j],_tp); } }}void dfs(ci x,ci y) { if(!y) return; dfs(pre[x][y].x,pre[x][y].y); qw(remap[b[y]],' ',true);}
Summary
二维树状数组查询和修改的操作。