# 75 条题解

• @ 2019-05-04 10:44:52

很简单，用一个数组把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 10ms 1.98 MiB
#2 Accepted 2ms 1.453 MiB
#3 Accepted 2ms 1.449 MiB
#4 Accepted 2ms 1.453 MiB
#5 Accepted 2ms 1.461 MiB
#6 Accepted 2ms 1.449 MiB
#7 Accepted 2ms 1.465 MiB
#8 Accepted 28ms 3.07 MiB
#9 Accepted 8ms 1.664 MiB
#10 Accepted 23ms 3.039 MiB
• @ 2018-03-31 10:42:26

# 状态 耗时 内存占用

#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;
}

``````
• @ 2017-08-07 21:16:50

思路易得，用一个数组把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;
}
``````
• @ 2020-11-14 16:44:40
``````/*
两次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;
}

``````
• @ 2017-08-27 21:42:04

//可以先处理一下原数组，然后用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;
}

• @ 2017-08-25 13:40:21

//思路：二分求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;
}
``````
• @ 2017-07-22 15:28:31
``````#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;
}

``````
• @ 2016-07-21 01:37:03

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

• @ 2016-10-25 17:38:14

为啥我把您的代码hack了啊QWQ，求看看
9 1
610977281
942318270
960666782
324874526
150749384
100008120
611172687
738589563
825745723

• @ 2016-01-26 12:09:12

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

• @ 2015-10-21 00:12:40

用一个数组把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.

• @ 2015-10-12 22:07:40

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

• @ 2015-09-15 21:19:14

/*

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;
}

• @ 2015-08-25 13:50:46

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

• @ 2014-08-24 21:57:48

测试数据 #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;
}

• @ 2014-08-24 21:20:12

测试数据 #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.

• @ 2014-08-15 21:23:45

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.

• @ 2014-08-15 12:10:45

cmi

• @ 2014-08-05 13:31:47

#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;
}

• @ 2013-08-11 10:47:37

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.

• @ 2013-08-11 10:49:03

厉害，牛！！！！！！！！！！！

• @ 2012-10-25 20:54:23

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.

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

ID
1369

7

3228

539

17%

3