1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cctype> 8 #include <cstdio> 9 #include <string>10 #include <vector>11 #include <cstdlib>12 #include <cstring>13 #include <iostream>14 #include <algorithm>15 using namespace std;16 typedef unsigned long long ull;17 typedef long long ll;18 const int inf = 0x3f3f3f3f;19 const double eps = 1e-8;20 const int maxn = 1e5+10;21 int dp[maxn],seg[maxn<<2];        //线段树区间求最值22 int a[maxn];23 void update(int l,int r,int pos,int x,int val)24 {25     if (l == r)26     {27         seg[pos] = val;28         return ;29     }30     int mid = (l + r) >> 1;31     if (x <= mid)32         update(l,mid,pos<<1,x,val);33     if (x > mid)34         update(mid+1,r,pos<<1|1,x,val);35     seg[pos] = max(seg[pos<<1],seg[pos<<1|1]);36 }37 int query(int l,int r,int pos,int x,int y)38 {39     if (x <= l && y >= r)40         return seg[pos];41     int mid = (l + r) >> 1;42     int ans1 = 0,ans2 = 0;43     if (x <= mid)44         ans1 = query(l,mid,pos<<1,x,y);45     if (y > mid)46         ans2 = query(mid+1,r,pos<<1|1,x,y);47     return max(ans1,ans2);48 }49 int main(void)50 {51     #ifndef ONLINE_JUDGE52         freopen("in.txt","r",stdin);53     #endif54     int n,d;55     while (~scanf ("%d%d",&n,&d))56     {57         memset(seg,0,sizeof(seg));58         int len = 0;59         for (int i = 0; i < n; i++)60         {61             scanf ("%d",a+i);62             a[i] += 2;                     //因为a[i]可能为0，而我的线段树是从1开始的所以加263             len = max(len,a[i]);64         }65         int ans = 1;66         for (int i = 0; i < n; i++)67         {68             dp[i] = query(1,len,1,1,a[i]-1) + 1;   //不能等于，所以减1，dp[i]表示以a[i]结尾的最长不降序列长度，69             if (i >= d)                            //延迟更新，这是这道题的关键，70                 update(1,len,1,a[i-d],dp[i-d]);71             ans = max(dp[i],ans);72         }73         printf("%d\n",ans);74     }75     return 0;76 }