Озадачен проблемой операции :(, нужна помощь ⇐ Python

[Anonymous]

Существует массив с его длиной (n) до 7500.
Мы можем выполнить следующую операцию один раз: < /p>
Выберите два целых числа l
и r так, что 1≤L≤r≤n
. Обратите внимание на порядок элементов, которые находятся между элементом L
-TH и элементом R
-Th в массиве, включительно.
Alice хочет измерить, насколько эффективен этот подход. Для каждого C = 0… N
Помогите Алисе найти количество различных операций (L, R
), которые приводят к точному проверяемым элементам C
. Две операции (L1, R1
) и (L2, R2
) отличаются, если L1 ≠ L2
или r1 ≠ r2
.
Я пытался решить эту проблему, но мог придумать только очень неэффективное решение: < /p>

Код: Выделить всё

N = int(input().strip())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))

ans = [0] * (N + 1)

prefix = [0] * (N + 1)
for i in range(1, N + 1):
prefix[i] = prefix[i - 1] + (1 if a[i - 1] == b[i - 1] else 0)

for l in range(N):
rev_a = a[:]
for r in range(l, N):
rev_a[l:r+1] = rev_a[l:r+1][::-1]

aff = 0
for i in range(l, r + 1):
if rev_a[i] == b[i]:
aff += 1

total = (
prefix[l]
+ aff
+ (prefix[N] - prefix[r + 1])
)
ans[total] += 1

rev_a[l:r+1] = rev_a[l:r+1][::-1]

print("\n".join(map(str, ans)))

Мне нужна помощь в оптимизации этого подхода, и любая помощь будет очень оценена.


Подробнее здесь: https://stackoverflow.com/questions/793 ... elp-needed