题意:
给你一个长度为n的序列v，你需要输出最长上升子序列，且要保证你选的两个相邻元素之间在原数组中的位置之差大于d
题解:
这个就是原来求最长上升子序列的加强版，这个思路和最长上升子序列的差不多
设dp[i]：截至到位置i能找到的最长上升子序列
对于一个位置i，我们要找截至到它的最长上升子序列，就需要for循环寻找dp[j]的最大值（且v[j]<v[i] 而且 1<=j<=i-1）
我们可以使用线段树来维护dp[j]的最大值
但是你发现dp[1],dp[2]...dp[i-1]中可能有某个位置k(1<=k<=i-1)满足，v[k]>v[i]，那么dp[k]我们就不可以去维护这个值
我们怎么解决这个问题？
我们可以按照v[k]的值把它的dp[k]放在线段树中的位置v[k]位置，这样就可以避免这个问题
代码：
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; #define rt root #define ls root<<1 #define rs (root<<1)|1 #define mem(a) memset(a,0,sizeof(a)) #define mem_(a) memset(a,-1,sizeof(a)) #define mem__(a) memset(a,INF,sizeof(a)) typedef long long ll; int tree[maxn<<2],arr[maxn],len[maxn]; int n,d; struct shudui { int val,id; } m[maxn]; bool mmp(shudui x,shudui y) { if(x.val!=y.val) return x.val<y.val; return x.id>y.id; } void push_up(int root) { tree[rt]=max(tree[ls],tree[rs]); } void update(int root,int L,int R,int pos,int val) { if(L==R) { tree[rt]=val; return; } int mid=(L+R)>>1; if(pos<=mid) update(ls,L,mid,pos,val); else update(rs,mid+1,R,pos,val); push_up(rt); } int query(int root,int L,int R,int LL,int RR) { if(LL<=L && R<=RR) { return tree[rt]; } int mid=(L+R)>>1,ans=0; if(LL<=mid) ans=max(ans,query(ls,L,mid,LL,RR)); if(RR>mid) ans=max(ans,query(rs,mid+1,R,LL,RR)); return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); int i,j,k,n; while(cin>>n>>k) { mem(tree); memset(len,0,sizeof(len)); int mx=-1; for(i=1; i<=n; i++) { cin>>arr[i]; if(arr[i]>mx)mx=arr[i]; } mx++; int ans=0; for(i=1; i<=n; i++) { //这个arr[i-k-1]+1就是为了保证严格上升子序列 if(i-k-1>0)update(1,1,mx,arr[i-k-1]+1,len[i-k-1]); if(arr[i]!=0)len[i]=query(1,1,mx,1,arr[i])+1;//arr[i]==0时查找会出现错误111111111111155t else len[i]=1; if(len[i]>ans)ans=len[i]; } cout<<ans<<endl; } } /* 5 0 3 1 5 2 3 len1=1 U 4 1 Q 1 1 1 len2=2 U 2 2 Q 1 5 3 len3=3 */