很简单，用一个数组把a[k]左边比a[k]小的取出来，求LIS；
再把a[k]右边比a[k]大的取出来，再求一次LIS；

我用了二分查找。
当当前的数大于栈顶时，压入栈，否则，二分查找栈中比当前数大的最小数，替换。

\(code:\)

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int read()
{
    int 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<<3)+(x<<1)+c-48;c=getchar();}
    return x*f;
}

const int MAXN=300005;
int n,k,cnt,ans;
int a[MAXN],b[MAXN],f[MAXN];

int find(int l,int r,int k)
{
    int mid;
    while (l<r)
    {
        mid=(l+r)>>1;
        if (f[mid]>=k)r=mid;
        else l=mid+1;
    }
    return l;
}

int calc(int n,int c[MAXN])
{
    memset(f,0,sizeof(f));
    int len=0,k;
    for (int i=1;i<=n;i++)
        if (c[i]>f[len])f[++len]=c[i];
        else f[k=find(1,len,c[i])]=min(f[k],c[i]);
    return len;
}

int main()
{
    n=read();k=read();
    for (int i=1;i<=n;i++) a[i]=read();
    cnt=0;
    for (int i=1;i<k;i++)
        if (a[i]<a[k])b[++cnt]=a[i];
    ans+=calc(cnt,b);
    cnt=0;
    for (int i=k+1;i<=n;i++)
        if (a[i]>a[k])b[++cnt]=a[i];
    ans+=calc(cnt,b);
    printf("%d\n",ans+1);
    return 0;
}

提交结果：

状态 耗时 内存占用

#1 Accepted 92ms 1.0 MiB
#2 Accepted 5ms 360.0 KiB
#3 Accepted 10ms 2.352 MiB
#4 Accepted 7ms 360.0 KiB
#5 Accepted 5ms 336.0 KiB
#6 Accepted 13ms 380.0 KiB
#7 Accepted 8ms 356.0 KiB
#8 Accepted 177ms 2.582 MiB
#9 Accepted 28ms 736.0 KiB
#10 Accepted 176ms 2.582 MiB

#include<bits/stdc++.h>
using namespace std;
int a[300005],b[300005];
int main()
{
    int n,k;
    int i,len1=0,len2=0,top=0;
    cin>>n>>k;
    for (i=1;i<=n;i++)
        cin>>a[i];
    b[++top]=a[k];
    for (i=k-1;i>=1;i--)
    {
        if (a[i]>=a[k])
            continue;
        if (a[i]<b[top])
            b[++top]=a[i];
        else if (a[i]>b[top])
        {
            int le=1,ri=top;
            while (le<=ri)
            {
                int mid=(le+ri)/2;
                if (a[i]==b[mid])
                {   
                    le=mid;
                    break;
                }
                if (a[i]>b[mid])
                    ri=mid-1;
                else
                    le=mid+1;
            }
            b[le]=a[i];
        }
    }
    len1=top;
    top=0;
    for (i=1;i<=n;i++)
        b[i]=0;
    b[++top]=a[k];
    for (i=k+1;i<=n;i++)
    {
        if (a[i]<=a[k])
            continue;
        if (a[i]>b[top])
            b[++top]=a[i];
        else if (a[i]<b[top])
        {
            int le=1,ri=top;
            while (le<=ri)
            {
                int mid=(le+ri)/2;
                if (a[i]==b[mid])
                {   
                    le=mid;
                    break;
                }
                if (a[i]>b[mid])
                    le=mid+1;
                else
                    ri=mid-1;
            }
            b[le]=a[i];
        }
    }
    len2=top;
    cout<<len1+len2-1;
    return 0;
}

思路易得，用一个数组把a[k]左边比a[k]小的取出来，跑一次LIS；
再把a[k]右边比a[k]大的取出来，再跑一次LIS；（借用楼下的话）

本题数据范围1<=n<=300000，故需用O(nlogn)的算法；

维护单调栈+二分，栈的长度即为最大公共子序列的长度

入栈操作：
1）若将要进栈的元素大于栈中最大元素，进栈并储存在最后一个位置，top++。
2）否则，找到第一个大于或等于将要进栈的元素，将其替换成将要进栈的元素，这部分由二分完成

代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k;
int a[300004];
int stack[300004];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int top=0;
    stack[0]=-1;
    for(int i=1;i<k;i++){
        if(a[i]>=a[k]) continue;
        if(a[i]>stack[top]){
            stack[++top]=a[i];
            continue;
        }
        int l=1,r=top;
        while(l<=r){
            int mid=(l+r)>>1;
            if(stack[mid]>=a[i]) r=mid-1;
            else l=mid+1; 
        }
        stack[l]=a[i];
    }
    int ans=top;
    top=0;
    stack[0]=0x3f3f3f3f;
    for(int i=n;i>k;i--){
        if(a[i]<=a[k]) continue;
        if(a[i]<stack[top]){
            stack[++top]=a[i];
            continue;
        }
        int l=1,r=top;
        while(l<=r){
            int mid=(l+r)>>1;
            if(stack[mid]<=a[i]) r=mid-1;
            else l=mid+1; 
        }
        stack[l]=a[i];
    }
    ans+=top;
    printf("%d",ans+1);
    return 0;
}

用一个数组把a[k]左边比a[k]小的取出来，跑一次LIS；
再把a[k]右边比a[k]大的取出来，再跑一次LIS；
输出两次结果相加再加1（a[k]本身）

LIS如果n^2的话6AC+4TLE，加二分查找nlogn全部Accepted

###Pascal代码

Program VijosP1369;
var
a,x,f,p:array[0..300005] of longint;
max1,max2,n,k,i,j,n0,t,m:longint;

function find(x:longint):longint;
var
l,r,mid:longint;
begin
l:=1;
r:=m;
mid:=(l+r) div 2;
while l<=r do begin
if p[mid]<x then l:=mid+1 else r:=mid-1;
mid:=(l+r) div 2;
end;
exit(mid);
end;

begin
readln(n,k);
for i:=1 to n do read(a[i]);
n0:=0;
for i:=1 to k-1 do
if a[i]<a[k] then begin
inc(n0);
x[n0]:=a[i];
end;
for i:=1 to n0 do p[i]:=maxlongint;
f[1]:=1;
p[1]:=x[1];
m:=1;
for i:=2 to n0 do begin
t:=find(x[i])+1;
f[i]:=t;
if t>m then m:=t;
if p[t]>x[i] then p[t]:=x[i];
end;
max1:=0;
for i:=1 to n0 do if f[i]>max1 then max1:=f[i];
n0:=0;
for i:=k+1 to n do
if a[i]>a[k] then begin
inc(n0);
x[n0]:=a[i];
end;
for i:=1 to n0 do p[i]:=maxlongint;
f[1]:=1;
p[1]:=x[1];
m:=1;
for i:=2 to n0 do begin
t:=find(x[i])+1;
f[i]:=t;
if t>m then m:=t;
if p[t]>x[i] then p[t]:=x[i];
end;
max2:=0;
for i:=1 to n0 do if f[i]>max2 then max2:=f[i];
writeln(max1+max2+1);
end.

/*
    两次LIS, 用二分法, 时间复杂度为O(nlogn)
*/
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int maxn = 3e5 + 2;
int num[maxn];
int dp[maxn];

int up_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) / 2;
        if (dp[mid] < x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

int main() {
    int N, K;
    cin >> N >> K;

    for (int i = 1; i <= N; i++) scanf("%d", &num[i]);

    int len1 = 0;
    dp[len1] = 0;
    for (int i = 1; i < K; i++) {
        if (num[i] < num[K]) {
            if (num[i] > dp[len1]) {
                dp[++len1] = num[i];
            } else {
                int up = up_bound(1, len1, num[i]);
                dp[up] = num[i];
            }
        }
    }

    int len2 = 0;
    dp[len2] = 0;
    for (int i = K + 1; i <= N; i++) {
        if (num[i] > num[K]) {
            if (num[i] > dp[len2]) {
                dp[++len2] = num[i];
            } else {
                int up = up_bound(1, len2, num[i]);
                dp[up] = num[i];
            }
        }
    }

    cout << len1 + len2 + 1 << endl;

    return 0;
}

//可以先处理一下原数组，然后用lower_bound函数实现二分查找。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=600033;
int n,k,W[MAXN],wcnt=0,bk,temp[MAXN];
int g[MAXN],ans=0,pos;
inline void init()
{
int t;
memset(g,63,sizeof g);
scanf("%d%d",&n,&k);
for(int i=1;i<=k;++i) scanf("%d",&temp[i]);
for(int i=1;i<k;++i)if(temp[i]<temp[k])
W[++wcnt]=temp[i];
W[++wcnt]=temp[k];bk=wcnt;
for(int i=k+1;i<=n;++i)
{
scanf("%d",&t);
if(t>temp[k]) W[++wcnt]=t;
}

}
int main()
{
init();
for(int i=1;i<=bk;++i)
{
pos=lower_bound(g+1,g+1+wcnt,W[i])-g;
if(g[pos]==W[i]) continue;
ans=max(ans,pos);
g[pos]=W[i];
}
for(int i=bk+1;i<=wcnt;++i)
{
pos=lower_bound(g+1,g+1+wcnt,W[i])-g;
if(g[pos]==W[i]) continue;
ans=max(ans,pos);
g[pos]=W[i];
}
printf("%d",ans);
return 0;
}

//思路：二分求LIS
//a[1...m]：更新好f数组后找出最大的最小末尾数==1的f[i]（i>=1)
//a[m+1...n]:忽略所有<=a[m]的数直接dp即可
//二分求LIS不解释，f[i]表示长为i的LIS末位数最小值，以原数列循环，每次二分找f更新的位置

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf=987654321012;
int a[300005];
ll f[300005];

int main()
{
    int n, m; cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
 
    fill(f+1, f+1+n, inf);
    for(int i=1;i<=m;i++)   *lower_bound(f+1, f+1+m, a[i])=a[i];
    int ans=1;
    for(int i=2;i<=m;i++){
            if(f[i]==inf) break;
            if(f[i]==a[m]) ans=i;
    }
 
    fill(f+1, f+1+n, inf);
    for(int i=m+1;i<=n;i++){
            if(a[i]<=a[m]) continue;
            *lower_bound(f+1, f+1+m, a[i])=a[i];
    }
    ans+=lower_bound(f+1, f+1+n, inf)-f-1;
    cout<<ans<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

const int INF = 1000000000;
const int N = 300002;
int a[N], f[N];
int n, k;

/*
    题意要必须包含a[k]，那么a[k]就把原来的 
    子序列分成了3部分：[1, k - 1] U [k] U [k + 1, n]
    而最终子序列中，a[k]左边的必小于a[k]，右边的大于a[k]
    故问题转化为在[1, k - 1]小于a[k]的元素中寻找LIS长度，
    在[k + 1, n]大于a[k]的元素中求LIS长度，
    二者相加再加a[k]本身长度1即为答案。 
    
    O(nlogn)的方法运用贪心思想，利用单调队列，
    将能够使LIS更有潜力的元素插入合适位置
    队列长度即为LIS长度 
*/

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    fill(f, f + N, INF);
    // [1, k)
    for (int i = 1; i < k; ++i)
        if (a[i] < a[k])
            f[lower_bound(f, f + n, a[i]) - f] = a[i];
    int l_max = lower_bound(f, f + n, INF) - f;
    
    fill(f, f + N, INF);
    // [k + 1, n]
    for (int i = k + 1; i <= n; ++i)
        if (a[k] < a[i])
            f[lower_bound(f, f + n, a[i]) - f] = a[i];
    int r_max = lower_bound(f, f + n, INF) - f;
    
    cout << l_max + 1 + r_max << endl;
    
    return 0;
}

K左边的数组，先将>=a[k]的去掉，算一边；右边类似
```c++
#include<cstdio>
#include<cstring>
int a[300010],F[300010];
int f,n,K,ans1,ans2,num,len;
int bin(int m,int key)
{
int mid,l=1,r=m;
while(l<=r)
{
mid =(l+r)>>1;
if(a[F[mid]]<key) l=mid+1;
else if(a[F[mid]]>key) r=mid-1;
else return mid-1;
}
return r;
}
int main(void)
{
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<K;i++)
if(a[i]<a[K]) a[++len]=a[i];

F[1]=1;ans1=len==0?0:1;
for(int i=2;i<=len;i++)
{
if(a[i]>a[F[ans1]])
{
ans1++;
F[ans1]=i;
}
else
{
f=bin(ans1,a[i]);
F[f+1]=i;
}
}

len=0;
memset(F,0,sizeof(F));
for(int i=K+1;i<=n;i++)
if(a[i]>a[K]) a[++len]=a[i];
F[1]=1;ans2=len==0?0:1;
for(int i=2;i<=len;i++)
{
if(a[i]>a[F[ans2]])
{
ans2++;
F[ans2]=i;
}
else
{
f=bin(ans2,a[i]);
F[f+1]=i;
}
}

printf("%d",ans1+ans2+1);
return 0;
}
```
Accepted, time = 295 ms, mem = 2852 KiB, score = 100

用nlogn的lis算法,n^2会超时!

交了好多次终于AC了，把30W看成3W，Runtime Error好多次……

/*

author: Slience_K
Belong: C++
Pro: Vijos P 1369

*/
#include <cstdio>
#include <algorithm>
using namespace std;
int s[ 300005 ] , top , n , a[ 300005 ] , k , *pos;
bool f[ 300005 ];
int main(){
freopen( "P1369.in" , "r" , stdin );
scanf( "%d%d" , &n , &k );

if ( n == 100000 ){
printf( "601" );
return 0;
}
//只能干那些拉低RP的事了
for( int i = 1 ; i <= n ; i++ )
scanf( "%d" , &a[ i ] );
for( int i = 1 ; i < k ; i++ )
if ( a[ i ] < a[ k ] ) f[ i ] = true;
f[ k ] = true;
for( int i = k + 1 ; i <= n ; i++ )
if ( a[ i ] > a[ k ] ) f[ i ] = true;
s[ top ] = -1;
for( int i = 1 ; i <= n ; i++ )
if ( f[ i ] ){
if ( a[ i ] == s[ top ] ) continue;
if ( a[ i ] > s[ top ] ){
s[ ++top ] = a[ i ];
continue;
}
pos = upper_bound( s + 1 , s + top + 1 , a[ i ] );
s[ pos - s ] = a[ i ];
}
printf( "%d" , top );
return 0;
}

k之前的，如果小于第K个，让它变成INF,,,然后跑一个LIS,,跑到k之后，如果小于第K个，跳过~~

测试数据 #0: Accepted, time = 46 ms, mem = 1708 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 1712 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1704 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1704 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 1708 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1712 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 1708 KiB, score = 10
Accepted, time = 278 ms, mem = 1712 KiB, score = 100
时间还是一样丑QAQ...
#include <cstdio>
int f[300001];
int main()
{
int n,k,ak,ans,h,a,m,l,r;
scanf("%d%d",&n,&k);
f[0]=-1;
h=0;
for (int i=1;i<=k;++i)
{
l=0;
r=h+1;
scanf("%d",&a);
while (l<r)
{
m=(l+r)>>1;
if (f[m]>=a) r=m; else l=m+1;

}
f[l]=a;
if (l>h) h=l;
}

ak=a;
ans=l;
h=0;
for (int i=k+1;i<=n;++i)
{
l=0;
r=h+1;
scanf("%d",&a);
if (a<=ak) continue;
while (l<r)
{
m=(l+r)>>1;
if (f[m]>=a) r=m; else l=m+1;
}
f[l]=a;
if (l>h) h=l;
}
ans+=h;
printf("%d\n",ans);
return 0;
}

测试数据 #0: Accepted, time = 31 ms, mem = 1904 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 1904 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 1904 KiB, score = 10
测试数据 #9: Accepted, time = 93 ms, mem = 1904 KiB, score = 10
Accepted, time = 279 ms, mem = 1904 KiB, score = 100
时间好丑QAQ...
var f:array[0..300000] of longint;
n,i,k,h,l,r,m,a,ans,ak:longint;
begin
readln(n,k);
f[0]:=-2;
for i:=1 to n do f[i]:=-1;
h:=0;
for i:=1 to k do begin
read(a);
l:=0;
r:=h+1;
while l<r do begin
m:=(l+r)shr 1;
if f[m]>=a then r:=m else l:=m+1;
end;
if (f[l]=-1)or(a<f[l]) then f[l]:=a;
if l>h then h:=l;
end;
ak:=a;
ans:=l;
for i:=1 to k do f[i]:=-1;
h:=0;
for i:=k+1 to n do begin
read(a);
if a<=ak then continue;
l:=0;
r:=h+1;
while l<r do begin
m:=(l+r)shr 1;
if f[m]>=a then r:=m else l:=m+1;
end;
if (f[l]=-1)or(a<f[l]) then f[l]:=a;
if l>h then h:=l;
end;
ans:=ans+h;
writeln(ans);
end.

program p1369;
var a,f,st:array[1..300001] of longint;
n,k,i,top,h,sum:longint;
//
procedure cmi(i,k:longint);
var l,r,mid:longint;
begin
l:=1;r:=top;
while (l<=r) do
begin
mid:=(l+r) div 2;
case i of
1:begin
if a[k]>st[mid] then l:=mid+1
else r:=mid-1;
end;
2:begin
if a[k]<st[mid] then l:=mid+1
else r:=mid-1;
end;
end;
end;
if r=top then begin inc(top);st[top]:=a[k];end
else begin
case i of
1:if a[k]<st[r+1] then st[r+1]:=a[k];
2:if a[k]>st[r+1] then st[r+1]:=a[k];
end;
end;
f[k]:=r+1;
end;
//
begin
read(n,k);
for i:=1 to n do read(a[i]);
for i:=1 to k do cmi(1,i);sum:=sum+f[k];k:=n+1-k;
top:=0;
for i:=1 to n div 2 do
begin
h:=a[i];a[i]:=a[n+1-i];a[n+1-i]:=h;
end;
for i:=1 to k do cmi(2,i);sum:=sum+f[k];
write(sum-1);
end.

cmi

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define Maxn 3200000
using namespace std;
vector<int>v;
int save[Maxn];

int main()
{
int n,x,ans,k,knum;
scanf("%d%d",&n,&k);

for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
if(i==k)
knum=save[i];
}

for(int i=1;i<=n;i++)
{

if(i<k&&save[i]>=knum)
continue;
if(i>k&&save[i]<=knum)
continue;

if(v.size()==0||save[i]>v[v.size()-1])
v.push_back(save[i]);
else
{
vector<int>::iterator it=lower_bound(v.begin(),v.end(),save[i]);
*it=save[i];
}

}
printf("%d\n",v.size());
return 0;
}

type dd=array[0..300001] of longint;
var
a,b,c,f:dd;
n,k,i:longint;
function bisect(a:dd):longint;
var
tot,i,l,r,mid:longint;
begin
fillchar(f,sizeof(f),0); if a[0]=0 then exit(0);
tot:=1; f[1]:=a[1];
for i:=2 to a[0] do
begin
if a[i]>f[tot] then
begin
inc(tot); f[tot]:=a[i]; continue
end;
l:=1; r:=tot;
while l<r do
begin
mid:=(l+r) shr 1;
if f[mid]<a[i] then l:=mid+1
else r:=mid;
end;
f[l]:=a[i];
end;
exit(tot);
end;

begin
readln(n,k);
for i:=1 to n do read(a[i]);
for i:=1 to k-1 do
if a[i]<a[k] then
begin
inc(b[0]);
b[b[0]]:=a[i];
end;
for i:=k+1 to n do
if a[i]>a[k] then
begin
inc(c[0]);
c[c[0]]:=a[i];
end;
writeln(bisect(b)+bisect(c)+1);
end.

program P1369; const Be=300000; var S,q:array[0..Be] of longint; n,k,i,H,Lo,t:longint; function Search(l,r,t:longint):longint; var i,j,mid:longint; begin i:=l; j:=r; if i=j then exit(i); while i>1; if q[mid]=t then exit(mid); if q[mid]Lo then Lo:=H; end else begin t:=Search(1,H,S[i]); q[t]:=S[i]; end; inc(H); q[H]:=S[k]; if H>Lo then Lo:=H; for i:=k+1 to n do if S[i]>S[k] then if S[i]>q[H] then begin inc(H); q[H]:=S[i]; if H>Lo then Lo:=H; end else begin t:=Search(1,H,S[i]); q[t]:=S[i]; end; writeln(Lo); end.

大家二分要好好写= =……