(luogu1704)寻找最优美做题曲线 [TPLY]

寻找最优美做题曲线

题目链接：https://www.luogu.org/problemnew/show/P1704

题目大意：

求包含指定点的最长不降子序列（严格递增）

题解

首先我们发现

一个序列中，如果某个数严格大于它之前的所有数，严格小于它之后的所有数，那么在寻找最长上升子序列是一定会包含这个数，否则将这个数加入序列中可以得到更长的上升子序列。

(摘自洛谷题解)

那么我们要从原数列中抠出这么一段序列使得我们指定的点一定被选

所以就好办了

在一段数列中，把每一个大于指定点而且在它前面的和小于指定点而且在它后面的删除

再对抠出来的数列做nlogn的求最长不降子序列长度（注意是严格递增，所以要特判等于的情况）

注意还要判impossible的情况

代码（原谅我代码风格变化了）

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#define rg register int

#define ll long long

#define RG register

#define il inline

using namespace std;

il int gi() {

  rg x=0,o=0;RG char ch=getchar();

  while(ch!='-'&&(ch<'0'||'9'<ch)) ch=getchar();

  if(ch=='-') o=1,ch=getchar();

  while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

  return o?-x:x;

}

int n,k,p[250001],a[500001],b[500001],stk[500001];

int main() {

    n=gi(),k=gi();

    for(rg i=1;i<=k;++i) p[i]=gi();

    sort(p+1,p+1+k);

    for(rg i=1;i<=n;++i) a[i]=gi();

    for(rg i=2;i<=k;++i)

        if(a[p[i-1]]>a[p[i]]) {

            puts("impossible");

            return 0;

        }

    for(rg i=1;i<=k;++i) {

        for(rg j=p[i-1]+1;j<=p[i]-1;++j)

            if(a[p[i-1]]<a[j]&&a[j]<a[p[i]])

                b[++b[0]]=a[j];

        b[++b[0]]=a[p[i]];

    }

    for(rg i=p[k]+1;i<=n;++i)

        if(a[i]>a[p[k]])

            b[++b[0]]=a[i];

    #define ub upper_bound

    rg top=1;

    stk[top]=b[1];

    for(rg i=2;i<=b[0];++i) {

        if(b[i]>stk[top]) stk[++top]=b[i];

        else {

            rg j=ub(stk+1,stk+1+top,b[i])-stk;

            if(stk[j-1]!=b[i]) stk[j]=b[i];

        }

    }

    printf("%d",top);

  return 0;

}