Nlogn最长XX子序列

题目：

我是超链接

二分。突然发现自己会写二分了

g数组单调递增，可以二分出最大的小于a[i]的位置，则g[j+1]=a[i]

由性质易得每次g[i]都会更改或者增加一个数字

那么同理的类比：

最长下降子序列:g结尾的最大数字，每次找最小的大于a[i]的位置

最长不降子序列:g结尾的最小数字，每次找最大且下标较大的小于等于a[i]的位置

代码：     

最长上升子序列（找到大于等于x的最小值

int lar=0; for (i=1;i<=n;i++) { int l=1,r=lar; while (l<=r) { int mid=(l+r)>>1; if (g[mid]<s[i]) l=mid+1; else r=mid-1; } g[r+1]=s[i]; lar=max(lar,r+1); } printf("%d\n",lar);

最长不上升子序列（找到小于x的最大值

int lar=0; for (i=1;i<=n;i++) { int l=1,r=lar; while (l<=r) { int mid=(l+r)>>1; if (g[mid]>=s[i]) l=mid+1; else r=mid-1; } g[r+1]=s[i]; lar=max(lar,r+1); } printf("%d",lar);

最长不下降子序列（找到大于x的最小值

int i,tot=0; for (i=1;i<=n;i++) { int l=1,r=tot; while (l<=r) { int mid=(l+r)>>1; if (g[mid]<=a[i]) l=mid+1; else r=mid-1; } g[r+1]=a[i]; tot=max(tot,r+1); } printf("%d",tot); 最长下降子序列（找到小于等于x的最大值

int maxx=0; for (i=1;i<=n;i++) { int l=1,r=maxx; while (l<=r) { int mid=(l+r)>>1; if (g[mid]>a[i]) l=mid+1; else r=mid-1; } g[r+1]=a[i]; maxx=max(maxx,r+1); }