w1049
2019-02-02 23:09:04
做这道题的时候看了很多题解，也没看懂，各种查终于弄明白了O(nlogn)的方法，自己来写一篇，试试能不能让更多人知道QwQ
注：树状数组做法请去别的大佬那里看，树状数组还是挺重要的。
这道题的做法很多，别的dalao题解里都有
dalao们也说了，根据"xxxx定理"，这题只需要求一个不上升序列长度和一个上升序列长度
我只说说如何找出它们的长度
写给萌新看，求dalao们轻喷(>﹏<)
(如果有锅请dalao们指出)
zhx曾经曰过，STL很慢
hja曾经曰过，觉得STL慢是以zhx为首的一批oi选手的偏见
我们不管他们曰过什么，只来看看这两个函数
这两个是STL中的函数，作用很相似：
假设我们查找x，那么：
lower_bound会找出序列中第一个大于等于x的数
upper_bound会找出序列中第一个大于x的数
没错这俩就差个等于号╮(╯▽╰)╭
以下都以lower_bound做栗子 (因为upper_bound做出的栗子不好吃)
(其实就是我懒得打两遍)
它们俩使用的前提是一样的：序列是有序的
对于一个数组a，在[1,n]的区间内查找大于等于x的数(假设那个数是y)，函数就写成：
lower_bound(a + 1, a + 1 + n, x);
函数返回一个指向y的指针
看着是不是很熟悉？回想sort使用的时候：
sort(a, a + 1 + n, cmp);这里a+1,a+1+n的写法是不是很像？
STL里面的函数写区间一般都这个尿性
同样的，lower_bound和upper_bound也是可以加比较函数cmp的：
lower_bound(a + 1, a + 1 + n, x, cmp);到这里不得不说说前面的"有序序列"，这里的"有序"是对什么有序？
你可能已经猜到了，它是对于比较器有序，并且必须是升序！
(为什么不是降序？这个你可能要去问问写STL的人)
一旦对降序序列使用lower_bound，就会出现神奇的错误，具体原因可以看这篇：
https://blog.csdn.net/qq1337715208/article/details/81072709
当然比较器默认也是"＜"
如果要在一个下降序列里寻找一个小于x的数呢？
根据我们之前说的，lower_bound只能对上升序列使用，那我假装下降序列是个上升序列就行了嘛～
(lower_bound：你当我傻吗)(w1049：没错我就当你傻)
只需要把比较器改成">"：
lower_bound(a + 1, a + 1 + n, x, cmp);同时需要写一个函数cmp：
bool cmp(const int& a,const int& b){return a > b;}当然，你也可以这样：
lower_bound(a + 1, a + 1 + n, x, greater <int> () );这里的greater<int>()就是c++友情提供的方便的大于函数，这样就不用自己动手写一个cmp函数了(其实就是懒)
它们的实现方式是二分查找 ，存在的意义就是让我们写代码更方便地偷懒(一行lower_bound比写二分查找方便多了)
众所周知，小葱非常擅长计算组合数返回的是个指针
对于返回值我们有两种处理方式：
许多人讨厌指针，那么我们用这个指针减去数组开头的指针(即数组名)，得到两个指针的差，就是数组下标，即：
int p = lower_bound(懒得写) - a;那么a[p]就是要找的y
(如果不知道为什么就记着好了)
指针好！指针秒！
改革春风吹满地，用指针的oier真争气！
(以上两行你可以当做什么都没看见)
int *p = lower_bound(还是懒得写);那么*p就是要找的y
可以看出指针多么直接，不像数组下标还要倒腾一遍
好像没什么可总结的QwQ
对一个下降序列a
int p = lower_bound(a + 1, a + 1 + n, x, greater <int> () ) - a;a[p]即a[1]到a[n]中第一个小于等于x的数
(被遗忘的upper_bound表示不服)
(即一套系统最多拦截数)(终于到二了)
首先我们需要一个数组a，存储从第1个到第n个导弹的高度
然后一个数组d(其实是个栈)，存储不上升序列
把a中的每个元素挨个加到d里面：
(a中第i个元素为a[i]，d长度为len，d中最后一个(也是最小的一个)为d[len])
d[++len] = a[i]但是我们发扬瞎搞精神：接的上要接，接不上创造条件也要接！
在d中找到第一个小于a[i]的数，把它踹了，用a[i]代替它！(为什么正确在下面）
假设这个数是y，怎样踹掉它呢？
很明显，我们需要使用lower_bound和upper_bound来查找
第一步，找一个听起来无比正确的理由，比如它占着位置不干活啦，干起活来还不如a[i]啦，naive啦，它too young啦，too simple啦......反正能骗过lower_bound和upper_bound就行
(lower_bound&&upper_bound：你当我们傻)(w1049：真聪明)
接下来，特别有正义感的lower_bound和upper_bound就会去把y给拎出来
第二步，考虑使用什么
我们知道，要求的是最大不上升子序列长度，也就是如果两个元素相等也是可以的
所以我们踹人就不用踹等于a[i]的了
结合上面，应该使用upper_bound(终于想起来它了)并且使用>作为比较器(这是个下降序列)
第三步，直接开搞
int p = upper_bound(d + 1, d + 1 + len, a[i], greater<int>()) - d;
d[p] = a[i];成功把a[i]塞了进去
显然成立
如果y在末尾，由于y < a[i]，所以y后面能接的不如a[i]多，y让位给a[i]可以让序列更长
如果y不在末尾，那y有生之年都不会再被用到了，直接踹了y就行，y咋样，who care？
注意到lower_bound只能在有序序列中使用，此时d还有序吗？
当然有序。(本文第一个句号)
假设y前一个y1，y后一个是y2，则
因为y是第一个小于a[i]的，所以
又因为
所以
对比下原来的式子
a[i]可以完美代替y，至于y以后咋办，who care？
对于最长上升子序列，只需要把上面的过程通通换一下符号
可以用以下方法证明：
反之亦然同理，推论自然成立，略去过程QED，由上可知证毕(多么美妙的证明)实际上，
for(int i=2;i<=n;i++)
if(d[len]>=a[i])d[++len]=a[i];
else {
int p=upper_bound(d+1,d+1+len,a[i],greater<int>())-d;
d[p]=a[i];
}最后len就是要求的最大不上升子序列长度
但要注意的是，d中存储的并不是最大不上升子序列！
原因如下：
即得易见平凡，仿照上例显然，留作习题答案略，读者自证不难在这里推荐一下DevC++的调试器(不用DevC++的当我没说)
（还是不要推荐了）
1.我们把a[i](389)加入d：
2.i=2，此时a[i](207)<=d[len](389)，把a[2]加入d：
3.i=3，此时a[i](155)<=d[len](207)，把a[3]加入d：
4.i=4，此时a[i](300)>d[len](155)，不能直接加入，所以准备踹人
5.找出d中第一个小于a[i](300)的(即207)，用a[i]换掉
6.i=5，此时a[i](299)>d[len](155)，不能直接加入，所以准备踹人
7.找出d中第一个小于a[i](299)的(即155)，用a[i]换掉
8.i=6，此时a[i](170)<=d[len](299)，把a[6]加入d：
9.i=7，此时a[i](158)<=d[len](170)，把a[7]加入d：
10.i=8，此时a[i](65)<=d[len](158)，把a[8]加入d：
至此，得到最大不上升子序列长度len=6
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], d1[N], d2[N], n;
int main() {
while (cin >> a[++n]); n--; //输入
int len1 = 1, len2 = 1; //初始长度为1
d1[1] = a[1]; //用于求不上升序列长度
d2[1] = a[1]; //用于求上升序列长度
for (int i=2; i<=n; i++) { //从a[2]开始枚举每个数(a[1]已经加进去了)
if (d1[len1] >= a[i]) d1[++len1] = a[i]; //如果满足要求(不上升)就加入d1
else { //否则用a[i]替换d1中的一个数
int p1 = upper_bound(d1 + 1, d1 + 1 + len1, a[i], greater<int>()) - d1;
d1[p1] = a[i];
}
if (d2[len2] < a[i]) d2[++len2] = a[i]; //同上
else {
int p2 = lower_bound(d2 + 1, d2 + 1 + len2, a[i]) - d2;
d2[p2] = a[i];
}
}
cout << len1 << endl << len2; //输出
return 0; //结束
}
更快速的版本：
#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register
using namespace std;
const int N=100010;
int a[N],d1[N],d2[N],n;
inline bool read(int &x) {
char c=getchar();
if(c==EOF)return false;
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9') {
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return true;
}
int main() {
while(read(a[++n]));n--;
R int len1=1,len2=1;
d1[1]=d2[1]=a[1];
for(R int i=2; i<=n; i++) {
if(d1[len1]>=a[i])d1[++len1]=a[i];
else *upper_bound(d1+1,d1+1+len1,a[i],greater<int>())=a[i];
if(d2[len2]<a[i])d2[++len2]=a[i];
else *lower_bound(d2+1,d2+1+len2,a[i])=a[i];
}
printf("%d\n%d",len1,len2);
return 0;
}一年过去，百感交集，虽然已经凉了，但是还是改正了一下这篇我唯一写的还行的题解里面的错误，祝各位在复活的NOIP中取得好成绩。
原来的代码return 0；中有个中文分号，现在已经没了。