题解 P1704 【寻找最优美做题曲线】

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq 题目描述-->[p1704 寻找最优美做题曲线](https://www.luogu.org/problemnew/show/P1704) ### 分析 首先需要明确的是,我们需要维护最长上升子序列.~~就像我的刷题记录~~ qwq 题目要求必须选一些位置,这些位置是必须选的. 所以我们需要考虑的是这些位置,两两之间的位置的合法性. 例如这样： 　　``蓝色部分必选.`` 中间部分均不合法.我们标记一下即可。  由于$p_i$不连续,所以我们需要$Sort$. 但是我们还**需要判断左右两端是否合法**.(这个坑死了. 求解单调递增序列的话就不多BB了.我这里用的是二分,并不是lower_bound #### 小声bb > 我们已经筛去了不合法的位置,所以合法位置一定是严格递增的。 > > 又因为我们必选位置一定会是其中的一员,因此这些必选位置一定会被选. ``代码`` ```c++ #include<cstdio> #include<algorithm> #include<cctype> #define R register using namespace std; inline void in(int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,stk[5000008],top,a[5000008]; int flg[5000008]; bool vis[5000008]; int main() { in(n),in(m);stk[0]=-1; for(R int i=1,x;i<=m;i++)in(flg[i]); for(R int i=1;i<=n;i++)in(a[i]),vis[i]=true; sort(flg+1,flg+m+1); for(R int i=1;i<m;i++) { if(a[flg[i]]>=a[flg[i+1]]) { puts("impossible"); return 0; } for(R int j=flg[i]+1;j<flg[i+1];j++) if(a[j]<=a[flg[i]] or a[j]>=a[flg[i+1]]) vis[j]=false; } for(R int i=1;i<flg[1];i++) if(a[i]>=a[flg[1]])vis[i]=false; for(R int i=flg[m]+1;i<=n;i++) if(a[i]<=a[flg[m]])vis[i]=false; for(R int i=1;i<=n;i++) { if(!vis[i])continue; if(a[i]>stk[top]) stk[++top]=a[i]; else { int l=1,r=top; while(l<=r) { int mid=(l+r)>>1; if(stk[mid]>a[i])r=mid-1; else l=mid+1; } stk[l]=a[i]; } } printf("%d",top); } ```