平方分割

コメントで教えてもらった方法を元に
下記のようにしました。
ただ、合わなかったけど。

K = int(input())
A = [int(input()) for _ in range(10000)]
ans = []
for i in range(0, 10000, 100):
    ans.append(max(A[i:i+100]))

for _ in range(K):
    minX,maxY = map(int,input().split())
    minX = int(minX ** 0.5)
    maxY = int(maxY ** 0.5)
    print(max(ans[minX:maxY]))

結局わからなかったのでタイムオーバーしたのでギブアップ。
どうやら後半考え方が間違っていたようで。。。
いや、どうやって調べようと思ってたが、よく考えたら100（N0.5乗）で割った商がAnsの該当する配列の要素の番目になるのか。

N,K = 10000, int(input())
root = int(N ** 0.5)
A = [int(input()) for _ in range(N)]
range_max = []
for i in range(0, 10000, 100):
    range_max.append(max(A[i:i+100]))
    
for _ in range(K):
    #左端の数値と右端の数値は出力から−１を引く
    left,right = map(lambda x:int(x) -1,input().split())
    #とりあえず配列Aのleft番目の要素を取得する
    ans = A[left]
    now = left
    #そのleft番目からright番目になるまで、１ずつループ
    while now <= right:
        # たとえば100ごとというのはスタートから100までがrightの中に入っていればその中の配列で最大値を出す
        if now % root == 0 and now + root - 1 <= right:
            ans = max(ans, range_max[now // root])
            now += root
        else:
            ans = max(ans, A[now])
            now += 1

    print (ans)