平方分割のバケット

ちょっとよくわからなかったので、色々調べながら。

（下記は引用）
max 関数は引数に list オブジェクトを渡すと、list オブジェクトに含まれる要素の最大値を返します。この際、計算量は O(N) です。

import math
A = [int(input()) for _ in range(10000)]
rootA =  int(math.sqrt(10000))
ans = [-1] * rootA

for i in range(rootA):
    start, end = 100 * i, 100 * (i + 1)
    ans[i] = max(A[start:end])

for val in ans:
    print(val)

たとえば、
１００＊１００の平方根ごとに分け、調べるグループを１００個ずつにして
そのなかでやりたい処理（たとえばこの問題なら１００個の中から最大値を選ぶ）
をやってそれを配列にいれる、というのを繰り返す。
こうすると、たとえば＊１００なので、
ループの1回目は0番目〜99番目、
ループの２回目は100番目〜199番目
ループの３回目だと200番目〜299番目
。。。と増えていく
だからそれぞれのグループの中で最大値がわかる。というわけ

なんで最初配列を入れるときに０ではなく−1かというと、フラグとして使われているから。
0だと予期しない挙動を返してしまうこともあり、−1としている。
↑ここらへんがよくわからなかったけど、−1じゃないといけないらしい。