题目描述

难度分:$1500$

输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

对于每个$i$，输出$j-i-1$的最大值，其中$j$满足$j \gt i$且$a[j] \lt a[i]$。如果不存在这样的$j$，输出$-1$。

输入样例$1$

6
10 8 5 3 50 45

输出样例$1$

2 1 0 -1 0 -1 

输入样例$2$

7
10 4 6 3 2 8 15

输出样例$2$

4 2 1 0 -1 -1 -1 

输入样例$3$

5
10 3 1 10 11

输出样例$3$

1 0 -1 -1 -1 

算法

离散化+线段树

这个题一看就可以用数据结构无脑做，本质上是一个二维偏序问题。

以数组中的元素值$a[i]$为索引开线段树$seg$，线段树$a[i]$位置存原数组中值为$a[i]$的最大索引$j$。这样就可以倒序遍历$i \in [1,n]$，当遍历到$i$时，在$seg$的$[1,a[i])$索引上查询最大值$j$，只要$j$是存在的，这个$i$位置就有答案$j-i-1$；否则当前位置的答案就是$-1$。接下来用$j$更新$seg$在$a[i]$索引处的最大值，更新完后遍历下一个$i$。

复杂度分析

时间复杂度

对$a[i]$做离散化由于涉及到排序，因此时间复杂度是$O(nlog_2n)$。初始化线段树的时间复杂度为$O(log_2n)$，倒序遍历$i \in [1,n]$的时间复杂度是线性的，对于每个$i$，需要在线段树上进行一次查询操作、一次更新操作，时间复杂度为$O(log_2n)$级别。因此，算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间的瓶颈在于线段树的消耗，线段树的空间复杂度在$O(4n)$级别，因此算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;
const int N = 200010;
int n, a[N];

class SegmentTree {
public:
    int arr[N];      // 初始数组
    struct Tag {
        int add;
        Tag() {
            add = 0;
        }
    };
    struct Info {
        int l, r, maximum;
        Tag lazy;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), maximum(val) {}
    } tr[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            tr[u] = Info(l, r, arr[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(u), l, mid);
        build(rc(u), mid + 1, r);
        pushup(u);
    }

    void modify(int l, int r, int d) {
        modify(1, l, r, d);
    }

    Info query(int l, int r) {
        return query(1, l, r);
    }

private:
    int lc(int u) { 
        return u<<1;
    }

    int rc(int u) {
        return u<<1|1;
    }

    void pushup(int u) {
        tr[u] = merge(tr[lc(u)], tr[rc(u)]);
    }

    void pushdown(int u) {
        if(not_null(tr[u].lazy)) {
            down(u);
            clear_lazy(tr[u].lazy);      // 标记下传后要清空
        }
    }

    void modify(int u, int l, int r, int d) {
        if(l <= tr[u].l && tr[u].r <= r) {
            set(u, d);
            return;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(mid >= l) modify(lc(u), l, r, d);
        if(mid < r) modify(rc(u), l, r, d);
        pushup(u);
    }

    Info query(int u, int l, int r) {
        if(l <= tr[u].l && tr[u].r <= r) return tr[u];
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l, info.r = rchild.r;
        info.maximum = max(lchild.maximum, rchild.maximum);
        return info;
    }

    // modify操作到不能递归时，设置节点的属性值
    void set(int u, int d) {
        tr[u].lazy.add += d;
        tr[u].maximum += d;
    }

    // 下传标记的规则
    void down(int u) {
        int mid = (tr[u].l + tr[u].r) >> 1;
        tr[lc(u)].lazy.add += tr[u].lazy.add;
        tr[rc(u)].lazy.add += tr[u].lazy.add;
        tr[lc(u)].maximum += tr[u].lazy.add;
        tr[rc(u)].maximum += tr[u].lazy.add;
    }

    // 判断标记是否为空的规则
    bool not_null(Tag& lazy) {
        return lazy.add != 0;
    }

    // 清空标记的规则
    void clear_lazy(Tag& lazy) {
        lazy.add = 0;
    }
};

int main() {
    scanf("%d", &n);
    vector<int> vals;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        vals.push_back(a[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int sz = vals.size();
    map<int, int> val2pos;
    for(int i = 0; i < sz; i++) {
        val2pos[vals[i]] = i + 1;
    }
    SegmentTree seg;
    for(int i = 0; i <= sz; i++) seg.arr[i] = 0;
    seg.build(1, 1, sz);
    vector<int> ans;
    for(int i = n; i >= 1; i--) {
        int index = val2pos[a[i]];
        int j = index > 1? seg.query(1, index - 1).maximum: 0;
        if(j > 0) {
            ans.push_back(j - i - 1);
        }else {
            ans.push_back(-1);
        }
        int t = seg.query(index, index).maximum;
        if(i > t) {
            seg.modify(index, index, i - t);
        }
    }
    reverse(ans.begin(), ans.end());
    for(int x: ans) printf("%d ", x);
    return 0;
}