Каосар та Сегменти (Розбір)

Рішення

Нам дана перестановка $[1,n]$. Очевидно, що максимальний елемент перестановки дорівнює $n$.

Нехай позиція $n$ у перестановці буде $i$ (індексація з 1). Будь-який неперервний підмасив (сегмент), який не містить $n$, матиме максимальне значення строго менше за $n$. Отже, лише сегменти, які повністю містяться в [1, i-1] (ліворуч від $n$) та [i+1, n] (праворуч від $n$), сприяють відповіді.

Нагадаємо, що кількість непорожніх підмасивів довжини $k$ дорівнює \frac{k(k+1)}{2}.

• Кількість допустимих сегментів ліворуч від $n$:

  \frac{i(i-1)}{2}

• Кількість допустимих сегментів праворуч від $n$:

  \frac{(n-i)(n-i+1)}{2}

Таким чином, загальна кількість сегментів, максимальне значення яких строго менше за максимальне значення перестановки, дорівнює:

Складність $O(n)$.

for _ in range(int(input())):
    n=int(input())
    p=list(map(int, input().split()))
    m=p.index(n)
    ans=0
    ans+=(m*(m+1))//2
    ans+=((n-m)*(n-m-1))//2
    print(ans)