题目地址：https://nanti.jisuanke.com/t/41303

题目：

简而言之，题目最终转化为求距a[i] 长度为k的范围内小于a[i]的最大值，然后递推求答案

 

解题思路：

方法1: set

遍历数组，动态得到以a[i]为中心的区间[i-k,i+k]，用set查询这个区间内第一个大于等于a[i]的值，它的前一个就是小于a[i]的最大值（如果有的话），代码简单好写。

方法2:线段树

读入时记录i所在的下标pos[i]，先建一个空线段树，i从1开始遍历到n，找到以i为中心的区间[pos[i]-k,pos[i]+k],查询区间最大值，得到的这个最大值一定是小于i的，且是以i为中心的区间内的最大值，就是我们要找的值，然后把i插入线段树中。

注意：区间的左右边界不要越界！

 

ac代码：

set：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+50;
int t,n,k,a[maxn],ans[maxn],pre[maxn];
set<int> s;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        s.clear();
        scanf("%d %d", &n, &k);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int l = 1, r = min(k+1, n);
        for(int i = 1; i <= r; i++)
            s.insert(a[i]);
        for(int i = 1; i <= n; i++)//a[i]左右两边小于a[i]的最大值
        {
            //扩右边
            while(r-i<k && r+1<=n) s.insert(a[++r]);
            //除左边
            while(i-l>k) s.erase(a[l++]);
            auto it = s.lower_bound(a[i]);
            if(it != s.begin()) pre[a[i]] = *(--it);
            else pre[a[i]] = 0;//没有找到比自己小的
        }
        ans[1] = 1, ans[0] = 0;
        for(int i = 2; i <= n; i++)
            ans[i] = ans[pre[i]] + 1;
        for(int i = 1; i <= n; i++)
        {
            if(i!=1) printf(" ");
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

线段树：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int val[maxn*4], a[maxn], pos[maxn], ans[maxn];
int t, n, k;
void push_up(int id)
{
    val[id] =  max(val[id<<1], val[id<<1|1]);
}
void build(int id, int l, int r)
{
    if(l == r)
    {
        val[id] = 0;
        return ;
    }
    int mid = (l+r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid+1, r);
    push_up(id);
}
int query(int id, int l, int r, int x, int y)
{
    if(x <= l && r <= y)
        return val[id];
    int mid = (l+r) >> 1, ans = 0;
    if(x <= mid) ans = max(ans, query(id << 1, l, mid, x, y));
    if(y > mid) ans = max(ans, query(id << 1 | 1, mid+1, r, x, y));
    return ans;
}
void change(int id, int l, int r, int pos, int v)
{
    if(l == r)
    {
        val[id] = v;
        return ;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) change(id << 1, l, mid, pos, v);
    if(pos > mid) change(id << 1 | 1, mid+1, r, pos, v);
    push_up(id);
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &k);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            pos[a[i]] = i;
            ans[i] = 0;
        }
        build(1, 1, n);
        for(int i = 1; i <= n; i++)
        {
            int l = max(1, pos[i]-k), r = min(n, pos[i]+k);
            int pre = query(1, 1, n, l, r);
            //cout << i << "  " << pre << endl;
            ans[i] = ans[pre] + 1;
            change(1, 1, n, pos[i], i);
        }
        for(int i = 1; i <= n; i++)
        {
            if(i!=1) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}