Возникла проблема с работой :(, нужна помощь ⇐ 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 = prefix + (1 if a == b 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 == b:
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)))
< /code>
Для ввода n = 3, a = [1, 3, 2] и b = [3, 2, 1] ответ [3, 3, 0, 0 ] Если Алиса выбирает (l = 1, r = 1
), (l = 2, r = 2
) или (l = 3, r = 3
), то элементы не будут проверял. Обратите внимание, что эти операции не изменяют ни одно из мест элементов.
Следующие операции приводят к тому, что один элемент проверяется. />: Алиса меняет порядок первого и второго элементов, поэтому новый состав будет [3,1,2]
. Первый элемент будет проверен.
для диапазонов L = 2, R = 3
: Алиса меняет порядок второго и третьего элементов, чтобы новый состав был [1,2,3]
. Второй элемент будет проверен.
для диапазонов L = 1, R = 3
: Алиса меняет порядок первого, второго и третьего элемента, поэтому новый состав будет [2,3,1 ]
. Третий элемент будет проверен.>

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