【题意】给一个序列，从右边开始看，对于第i个数字a[i]，在右边找到一个比它小（严格小）的，最靠右的位置，k，输出k-i-1，如果一个都找不到，输出-1。对于序列的每个元素都要输出。

【解题方法1】 线段树。节点保存最小值，每次把节点更新为INF，然后查找整个区间最右边比它小的数的位置。

【代码1】


int n, a[maxn];
struct node{
    int l, r, v;
}T[maxn*4];
void pushup(int rt)
{
    T[rt].v = min(T[rt*2].v, T[rt*2+1].v);
}
void Build(int l, int r, int rt)
{
    T[rt].l = l, T[rt].r = r;
    if(l == r){
        T[rt].v = a[l];
        return;
    }
    int mid = (l + r) / 2;
    Build(l, mid, rt * 2);
    Build(mid + 1, r, rt * 2 + 1);
    pushup(rt);
}
void update(int pos, int rt){
    if(T[rt].l == T[rt].r){
        T[rt].v = INF;
        return ;
    }
    int mid = (T[rt].l + T[rt].r) / 2;
    if(pos <= mid) update(pos, rt * 2);
    else update(pos, rt * 2 + 1);
    pushup(rt);
}
int queryans(int x, int rt){
    if(T[rt].l == T[rt].r){
        return T[rt].l;
    }
    if(T[rt * 2 + 1].v < x) return queryans(x, rt * 2 + 1);
    else return queryans(x, rt * 2);
}
int main()
{
    cin >> n;
    REP2(i, 1, n) cin >> a[i];
    Build(1, n, 1);
    REP2(i, 1, n){
        update(i, 1);
        if(T[1].v >= a[i]) cout << "-1" << " ";
        else cout << queryans(a[i], 1) - i - 1 << " ";
    }
    cout << endl;
}


【解题方法2】 单调队列。我们需要维护一个序列，这个序列保存着已扫描的值里面的最小值，同时这个序列具有单调性，从开始到当前，序列需要保持递减，对于插入的时候如果无法保持序列的单调性的话，就不要需要插入的值，否则就插入。在求结果的时候，我们可以二分求出比考察点小的，里考察点最远(最右)的那个点，然后求出答案即可。


int n, a[maxn], ans[maxn];
vector <int> v, pos;
int main()
{
    cin >> n;
    REP1(i, 0, n) cin >> a[i];
    REP3(i, n - 1, 0){
        if(v.size() == 0 || v.back() >= a[i]){
            v.push_back(a[i]);
            pos.push_back(i);
            ans[i] = -1;
        }
        else{
            int j = lower_bound(v.rbegin(), v.rend(), a[i]) - v.rbegin();
            j =(int) v.size() - j;
            ans[i] = pos[j] - i - 1;
        }
    }
    REP1(i, 0, n) cout << ans[i] << " ";
}