我们先找到每个点的右边第一个比它大的， 然后从大的往它建边， 然后可以发现这是一棵树。

我们令d[ i ] 为 i 号点往上走最多能走几步， 我们能用线段树维护d 的值。

我们加入点 i 的时候， 我们把它的值设为 d[ fa ] + 1， 我们删除 i 的时候， 把 i 这棵子树中的d 都减 1, 

每次询问最大值就好啦。

#include
     
      #define LL long long#define LD long double#define ull unsigned long long#define fi first#define se second#define mk make_pair#define PLL pair
      
       #define PLI pair
       
        #define PII pair
        
         #define SZ(x) ((int)x.size())#define ALL(x) (x).begin(), (x).end()#define fio ios::sync_with_stdio(false); cin.tie(0);using namespace std;const int N = 1e6 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-8;const double PI = acos(-1);template
         
           inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}template
          
            inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}template
           
             inline bool chkmax(T& a, S b) { return a < b ? a = b, true : false;}template
            
              inline bool chkmin(T& a, S b) { return a > b ? a = b, true : false;}int n, k, to[N], a[N];vector
             
               G[N];int in[N], ot[N], idx;vector
              
                ans;struct SegmentTree {#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1 int mx[N << 2], lazy[N << 2]; inline void pull(int rt) { mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]); } inline void push(int rt) { if(lazy[rt]) { mx[rt << 1] += lazy[rt]; mx[rt << 1 | 1] += lazy[rt]; lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; } } void update(int L, int R, int val, int l, int r, int rt) { if(R < l || r < L || R < L) return; if(L <= l && r <= R) { mx[rt] += val; lazy[rt] += val; return; } push(rt); int mid = l + r >> 1; update(L, R, val, lson); update(L, R, val, rson); pull(rt); } void setVal(int p, int val, int l, int r, int rt) { if(l == r) { mx[rt] = val; return; } push(rt); int mid = l + r >> 1; if(p <= mid) setVal(p, val, lson); else setVal(p, val, rson); pull(rt); } int query(int L, int R, int l, int r, int rt) { if(R < l || r < L || R < L) return 0; if(L <= l && r <= R) return mx[rt]; push(rt); int mid = l + r >> 1; return max(query(L, R, lson), query(L, R, rson)); }} Tree;void dfs(int u) { in[u] = ++idx; for(auto& v : G[u]) dfs(v); ot[u] = idx;}int main() { scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); stack
               
                 stk; for(int i = n; i >= 1; i--) { while(SZ(stk) && a[stk.top()] <= a[i]) stk.pop(); to[i] = SZ(stk) ? stk.top() : n + 1; stk.push(i); G[to[i]].push_back(i); } dfs(n + 1); for(int i = n; i > n - k; i--) { Tree.setVal(in[i], Tree.query(in[to[i]], in[to[i]], 1, n + 1, 1) + 1, 1, n + 1, 1); } ans.push_back(Tree.mx[1]); for(int i = n - k; i >= 1; i--) { Tree.update(in[i + k], ot[i + k], -1, 1, n + 1, 1); Tree.setVal(in[i], Tree.query(in[to[i]], in[to[i]], 1, n + 1, 1) + 1, 1, n + 1, 1); ans.push_back(Tree.mx[1]); } reverse(ALL(ans)); for(int i = 0; i < SZ(ans); i++) printf("%d%c", ans[i], " \n"[i == SZ(ans) - 1]); return 0;}/**/