传送门：小明系列问题——小明序列
题意：有n个数，求间距大于d的最长上升序列。
分析：dp[i]表示在i点以a[i]结束距离大于d的最长上升序列，然后每更新到第i点时，取i-d之前小于a[i]的数为结束的最长上升序列进行状态转移，并维护前i-d之前的最大上升序列，维护i-d之前的每点为结束的最长上升序列用线段树维护即可。
#pragma comment(linker,"/STACK:1024000000,1024000000") #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <limits.h> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 100010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; inline int read() { char ch=getchar(); int x=0; while(ch>'9'||ch<'0')ch=getchar(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x; } int dp[N],a[N]; int mx[N<<2]; void pushup(int rt) { int ls=rt<<1,rs=ls|1; mx[rt]=max(mx[ls],mx[rs]); } void build(int l,int r,int rt) { mx[rt]=0; if(l==r)return; int m=(l+r)>>1; build(lson); build(rson); } void update(int pos,int c,int l,int r,int rt) { if(l==r) { mx[rt]=max(mx[rt],c); return; } int m=(l+r)>>1; if(pos<=m)update(pos,c,lson); else update(pos,c,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return mx[rt]; int m=(l+r)>>1; int res=0; if(L<=m)res=max(res,query(L,R,lson)); if(m<R)res=max(res,query(L,R,rson)); return res; } int main() { int n,d; while(scanf("%d%d",&n,&d)>0) { build(0,N,1); for(int i=1;i<=n;i++)dp[i]=1; int ans=1; for(int i=1;i<=n&&i<=d;i++) { //scanf("%d",&a[i]); a[i]=read(); } for(int i=d+1;i<=n;i++) { //scanf("%d",&a[i]); a[i]=read(); if(a[i]>0)dp[i]=query(0,a[i]-1,0,N,1)+1; else dp[i]=1; update(a[i-d],dp[i-d],0,N,1); ans=max(ans,dp[i]); } printf("%d ",ans); } }