【模版】二分查找、最长上升子序列(LIS)、最长下降子序列模版

二分：lower_bound()在first和last二分查找（前闭后开），返回第一个大于等于x的位置upper_bound()返回第一个大于x的位置区别：和，即保持非降序的第一个可

二分：

lower_bound()在first和last二分查找（前闭后开），返回第一个大于等于x的位置

upper_bound()返回第一个大于x的位置

区别：>=和>，即保持非降序的第一个可安插位置和最后一个可安插位置

int lowerBound(int x){ int l=1,r=n; while(l<=r){ int mid=(l+r)>>1; if (x>g[mid]) l=mid+1; else r=mid-1; } return l;}int upperBound(int x){ int l=1,r=n; while(l<=r){ int mid=(l+r)>>1; if (x>=g[mid]) l=mid+1; else r=mid-1; } return l;}

扩展（非增序列二分）：

rev_lower_bound()在first和last二分查找（前闭后开），返回第一个小于等于x的位置

rev_upper_bound()返回第一个小于x的位置

注意代码中if语句判断条件的区别

int revLowerBound(int x){ int l=1,r=n; while(l<=r){ int mid=(l+r)>>1; if (rg[mid]>x) l=mid+1; else r=mid-1; } return l;}int revUpperBound(int x){ int l=1,r=n; while(l<=r){ int mid=(l+r)>>1; if (rg[mid]>=x) l=mid+1; else r=mid-1; } return l;}

最长上升子序列(LIS)

定义dp[i]为以i结尾的最长上升子序列长度，则dp[i]=max{0,d[j] | j最长下降子序列(代码求的是原序列的最长不下降子序列)

定义dp[i]为以i结尾的最长下降子序列长度，则dp[i]=max{0,d[j] | js[j]}+1

最长下降子序列（=)

int s[maxn],n;int dp[maxn],g[maxn];int main(){ while(scanf("%d",i

补充：

1.关于 (L+R)>>1 与 L+(R-L+1)/2的区别

(L+R)>>1取下界 L+(R-L+1)/2取上界

例如L=10，R=11，则mid=10.5 左10右11

while(L>1) if (check(mid)) L=mid; else R=mid-1; } while(L>1; if (!check(mid)) L=mid+1; else R=mid; } //ans=L