CodeForces 91B Queue （線段樹單點操作）

CodeForces 91B Queue （線段樹單點操作）

Description

There are n walruses standing in a queue in an airport. They are numbered starting from the queue's tail: the 1-st walrus stands at the end of the queue and the n-th walrus stands at the beginning of the queue. The i-th walrus has the age equal to a_i.

The i-th walrus becomes displeased if there's a younger walrus standing in front of him, that is, if exists such j (i?j), that a_i?>?a_j. The displeasure of the i-th walrus is equal to the number of walruses between him and the furthest walrus ahead of him, which is younger than the i-th one. That is, the further that young walrus stands from him, the stronger the displeasure is.

The airport manager asked you to count for each of n walruses in the queue his displeasure.

Input

The first line contains an integer n (2?≤?n?≤?10⁵) — the number of walruses in the queue. The second line contains integers a_i (1?≤?a_i?≤?10⁹).

Note that some walruses can have the same age but for the displeasure to emerge the walrus that is closer to the head of the queue needs to be strictly younger than the other one.

Output

Print n numbers: if the i-th walrus is pleased with everything, print "-1" (without the quotes). Otherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest from him younger walrus.

Sample Input

6
10 8 5 3 50 45

2 1 0 -1 0 -1 

7
10 4 6 3 2 8 15

4 2 1 0 -1 -1 -1 

5
10 3 1 10 11

1 0 -1 -1 -1 

線段樹維護區間最小值， 循環一遍數組，每次找到比這個數小且在最右端的數，那麼左邊處理過的數可以更新成INF， 順便更新最小值。那麼查詢之前， 先詢問整個數組的最小是和當前值的比較，滿足最小值小於當前值才有查詢的必要，而且右邊不成立就一定在左邊。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef __int64 LL;
const int maxn = 100005;
const int MAX = 0x3f3f3f3f;
int n, tg, b, k, a[maxn], mi[maxn << 2], ans[maxn];
void up(int o) {
    mi[o] = min(mi[o<<1], mi[o<<1|1]);
}
void build(int o, int l, int r) {
    if(l == r) {
        scanf("%d", &mi[o]);
        a[l] = mi[o];
        return;
    }
    int m = (l+r) >> 1;
    build(lson);
    build(rson);
    up(o);
}
void query(int o, int l, int r) {
    if(l == r) {
        ans[k++] = l - b - 1;
        return;
    }
    int m = (l+r) >> 1;
    if(mi[o<<1|1] < tg) query(rson);
    else query(lson);
}
void update(int o, int l, int r) {
    if(l == r) mi[o] = MAX;
    else {
        int m = (l+r) >> 1;
        if(b <= m) update(lson);
        else update(rson);
        up(o);
    }
}
int main()
{
    cin >> n;
    build(1, 1, n);
    for(int i = 1; i <= n; i++) {
        tg = a[i], b = i;
        update(1, 1, n);
        if(mi[1] >= tg) ans[k++] = -1;
        else query(1, 1, n);
    }
    for(int i = 0; i < k; i++) printf("%d ", ans[i]);
    return 0;
}