题解 P1704 【寻找最优美做题曲线】
分析题目
由于对于题目本身没用的信息太多，但是毕竟是洛谷原创我还是概括一下：
和题目无关的：
洛谷有一个强大功能即自动绘制出每天做题的数量的曲线提醒我是个废物。
以及nodgd奆佬有强迫症，每天都必须比前一天刷的题多（甚至一天十亿道题），不仅如此，他还可以预测自己未来的行为 （因此他获得了几次彩票头奖）
上面全是瞎扯，下面才是正题
鄙人不才，如果有疏漏请指出。
题目大意：
给定一个N个元素的序列，求有某些限制的最长上升子序列。
题目限制：
给定其中的一些位置，要求这些位置必须在最长上升子序列中。
例子：
下面这个序列
1 5 2 3 6 9
在没有任何限制条件的情况下，最长上升子序列为
1 2 3 6 9
如果我们固定要选第二个元素的话，其有限制的最长上升子序列为
5 6 9
无限制求法
要想知道怎么求有限制的首先还是得知道怎么求没有限制的。
第一种方法是动态规划，由于没啥用直接省去。如果有需要可以百度。复杂度为平方级别。
第二种方法也就是用的最多的方法，贪心+二分。
算法流程：
从头开始遍历每一个原来的元素，然后在最长子序列数组中，将大于等于这个遍历到的元素的第一个元素的位置直接改为这个元素。（有一点绕）
例如目前有一个上升子序列 2 3 6 9，
然后我扫描到了一个7，
于是我找到上升子序列中的9将它改成7。
特别的，如果没有大于等于它的元素，便直接将它插入到上升子序列的末尾。
最后我们得到的上升子序列就是最长的了。
强行解释：
贪心原理：对于一个上升子序列，在长度相同的情况下，其末尾的元素越小，越有利于接下来的增长。
例如，序列2 3 5是比序列2 3 9更优的（想象这三个元素后面还有一个元素7）。
正确性显然
为了简化代码，我们不需要判断当前元素是否可以放到上升子序列的末尾，每一次直接替换掉大于等于它的第一个元素。等于可以排除两个相等的元素的影响，避免序列中出现两个相同的元素使答案错误。
正确性依然显然
找大于等于他的第一个元素直接用二分查找即可。
栗子
我们讨论以下这个序列：
1 5 3 7 4 6
显然他的最长上升子序列是1 3 4 6
首先找到第一个元素1，由于现在上升子序列中没有元素（相当于没有大于等于它的），直接插入。然后上升子序列变为1。
接着找到第二个元素5，也没有大于等于它的，直接插入。上升子序列变为 1 5。
接着找到第三个元素3，根据贪心原理，找到第一个大于等于它的元素5，将5改为3。上升子序列变为1 3。
然后找到第四个元素7，插入最后。上升子序列变为1 3 7。
然后找到第五个元素4，通过上述方法把7改成4。上升子序列变为1 3 4。
最后找到第六个元素6，插入最后。上升子序列变为1 3 4 6。
至此，算法完美结束。
有没有体会到一点？
有限制后的求法
由于有一些元素是必须选择的，我们的算法需要有所调整。
首先我们通过一张图直观的看看在两个必须选择的元素中间有哪些是显然不会被选择的。
图中橙色的1 2 4号都是不可能被选择的。
因为1号和二号比必选1更小，要求序列严格上升，因此不可能出现在最终答案里面。但是由于上面的算法会用它们去替换上升子序列中更大的元素甚至是必选的元素，因此遍历它们会导致答案的错误。
而4号比必选2更大，如果要选择必选2元素，4号不可能出现在最终答案里面。同样的，如果用上面的算法会把他们直接插入上升子序列的最后，直接导致答案的错误。
他们对答案没有贡献，且会导致最终答案计算错误。
而3号和5号的大小介于两个必选之间，都是可能被选择的。
根据上述分析，我们只需要删去两个必选之间比前一个必选更小的和比后一个必选更大的所有数（打一个标记就行），然后跑一遍之前说的没有限制的算法就可以得到最后的答案了。由于输入必选的元素编号不保证有序，我们需要排一次序。
无解的情况当且仅当必选的子序列不是单调上升的。（显然）
在打代码的时候需要注意细节，第一个必选之前和最后一个必选之后的区间也需要考虑。
代码
代码中使用了C++中的STL函数 lower_bound
使用 lower_bound(a+1,a+n+1,x)-a 可以返回a数组中第一个大于等于x的数的下标。（首地址减去尾地址才能得到下标）
upper_bound和它使用方法相同，只不过返回第一个大于x的数的下标。
简直是懒人福利啊，在离散化中也可以使用它们简化代码。
当然，a数组必须是有序的。
码风奇怪，代码仅供参考。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,a[1000001],p[1000001],cnt,t[1000001];
bool b[1000001];
int main()
{
cin>>n>>k;
for(int i=1;i<=k;i++)
scanf("%d",&p[i]);//读入必选的元素，排序。
sort(p+1,p+k+1);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=k;i++)//无解的情况当且仅当必选的子序列不是单调上升的
{
if(a[p[i]]<=a[p[i-1]])
{
cout<<"impossible"<<endl;
return 0;
}
}
p[k+1]=n+1;
a[n+1]=1e9+5;//第一个必选之前和最后一个必选之后的区间也需要考虑
for(int i=1;i<=n;i++)//删去对答案没有贡献且会导致答案出现错误的元素
{
if(p[cnt+1]==i)
{
cnt++;
continue;
}
if(a[i]<=a[p[cnt]]||a[i]>=a[p[cnt+1]])b[i]=1;
}
cnt=0;//反复利用
for(int i=1;i<=n;i++)
{
if(b[i])continue;//跳过标记的元素
if(a[i]>t[cnt])//正常的最长上升子序列算法
{
t[++cnt]=a[i];
}
else
{
int x=lower_bound(t+1,t+cnt+1,a[i])-t;//正常的二分
t[x]=a[i];
}
}
cout<<cnt<<endl;//正常的输出
return 0;//非同寻常的退出程序
}如果你有幸看到了这篇题解的最后，就说明你觉得我的题解有帮助。这是我熬夜赶出来的题解（现在已经晚上11点了明天还要上课），所以为啥不点个赞呢？（真是无耻）