nlogn最长不下降序列及严格递增

``` //最长不下降子序列nlogn Song #include<cstdio> #include<algorithm> using namespace std; int a[40005]; int d[40005]; int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); if (n==0) //0个元素特判一下 { printf("0\n"); return 0; } d[1]=a[1]; //初始化 int len=1; for (int i=2;i<=n;i++) { if (a[i]>=d[len]) d[++len]=a[i]; //如果可以接在len后面就接上，如果是最长上升子序列，这里变成> else //否则就找一个最该替换的替换掉 { int j=upper_bound(d+1,d+len+1,a[i])-d; //找到第一个大于它的d的下标，如果是最长上升子序列，这里变成lower_bound d[j]=a[i]; } } printf("%d\n",len); return 0; } ``` 一道模板题[p3902递增](https://www.luogu.org/problem/P3902) 更新 2019/9/26 一种求最大严格递增的方法 ： 将序列A[i]-i; 相同的数就被cut掉了 而数列递增的数也一定存在递增关系 上面这一行还不是很理解所以这种方法先当结论记住吧 ``` #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,len; int a[N],dp[N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]-=i; dp[++len]=a[1]; for(int i=2;i<=n;i++){ if(dp[len]<=a[i]) dp[++len]=a[i]; else{ int k=lower_bound(dp+1,dp+len+1,a[i])-dp; dp[k]=a[i]; } } printf("%d",n-len); } ```