https://www.acmicpc.net/problem/2517
1秒、256 MBメモリ
input :

n (3 ≤ n ≤ 500000)

選手たちの普段の実力

output :

入力は、与えられた選手の順序と同じ順序で、行毎に

が出力.
条件:

普段は実力が自分より劣っている選手が先頭に立つと、残りの距離でリードする可能性がある.

より大きな価格はより良い実力を意味します

現在の手順で入力し、各選手のベストレベルを算出します.

最も注目されるのはarrayを用いて二分探索を行い,insertを用いて整列配列を作成することである.
しかし,すべてのinsertメソッドの時間的複雑さはO(n)であるため,タイムアウトが発生する.
treesetのような状況は、インデックスを保存しないための問題かもしれません.
これらの問題については、セグツリーを使っている人がたくさんいますが、理解しにくいです...
フィンウィックの木を使った草もあったので見て勉強しました.
2517の回答
フィンウィックについての説明
これらを見て、3点をまとめました.

問題の考え方

近づいた最大のアイデアはこれです.
私の前を走っている人の中には、私よりレベルが低い人が何人かいます.
このような探索によって,自分のレベルを知ることができ,これが優先的に考慮される問題である.
では、木で表すとしたら?
セグトリ、フィンウィックトリの意味は、高速計算部分と.
インデックスごとに、自分より実力の低い人を見るのは、自分より実力の低い人がどれだけいるかを確認することに等しい.
変更の方法は、現在自分の実力がある場合、このインデックスから実力の人数を数え、インデックスから削除することです.
自分の実力については、まだ計算していないので、大丈夫です.

フィンウィックの木

sumとaddの2つの関数から構成されています.addの場合、update関数に変更したいです.

sumの場合

「ワールドカップ」は、これまで選手たちの等級を記録しており、フィンウィックの木の保存方法で保存されている.
このインデックスのインデント方式は覚えておいてください.
今の13よりも実力の低い選手を探しているなら
13(1101)->12(1100)->8(1000).
減算(インデックス&インデックス-1)またはインデックス-を減算する方法を使用します.
(インデックス&-インデックス)は不可能です.8、4など2の平方数の場合でも、独自のものがあるからです.

updateの場合

今は自分の実力を+1にして、後ろの選手に上記の過程で演算できるようにしなければならない.
3寸の実力のあるやつを保存したいなら(長さが16になるまで)
3(11)->4(100)->8(1000)->16(10000).
このとき2の報酬が増加するので,インデックス+(インデックス&インデックス)で実現する.
該当するインデックス(人数表示)から自分より実力の低い人を除けば、それがベストレベルです.

n/a.実力

実力は同じで、これ以上調整しないとメモリの問題が大きくなります.
10億の範囲があるので、ここに穴があります.
つまり、選手の数は50万しかない.
したがって,実力については,並べ替えにより値を再付与する過程が必要である.
その後、インデックスでソートして、順番に実行すればいいです.

import sys

def sum(pos):
    ret = 0

    while pos > 0:
        ret += tree[pos]
        pos = pos & (pos - 1)

    return ret

def update(pos):
    while pos <= n:
        tree[pos] += 1
        pos += (pos & -pos)

n = int(sys.stdin.readline())
data, tree = [], [0] * (n + 1)

for i in range(n):
    temp = int(sys.stdin.readline())
    data.append([temp, i])

data.sort()
for i in range(1, n + 1):
    data[i - 1][0] = i

data.sort(key=lambda x:x[1])
for i in range(1, n + 1):
    val, idx = data[i - 1]
    print(i - sum(val))
    update(val)