Kaosar və Seqmentlər#12325

Kaosar və Seqmentlər (Həll təhlili)

Problem Müəllifi:	AlKaosar Hussain
Hazırlayan:	AlKaosar Hussain
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bize $[1, n]$ permutasiya verilir. Aydındır ki, permutasiyanın maksimum elementi $n$ -dir.

$n$ -nin permutasiyadakı mövqeyini $i$ (1-dən başlayan indeksləşdirmə) olaraq qəbul edək. $n$ -ni daxil etməyən hər hansı ardıcıl alt massiv (seqment) $n$ -dən kiçik maksimuma sahib olacaq. Buna görə də, yalnız $[1, i - 1]$ [1, i-1] (n-in solunda) və $[i + 1, n]$ [i+1, n] (n-in sağında) tamamilə yerləşən seqmentlər cavaba töhfə verir.

Xatırladaq ki, uzunluğu $k$ olan boş olmayan alt massivlərin sayı $\frac{k ( k + 1 )}{2}$ \frac{k(k+1)}{2}-dir.

$n$ -nin solundakı etibarlı seqmentlərin sayı:
$\frac{i ( i - 1 )}{2}$
\frac{i(i-1)}{2}
$n$ -nin sağındakı etibarlı seqmentlərin sayı:
$\frac{( n - i ) ( n - i + 1 )}{2}$
\frac{(n-i)(n-i+1)}{2}

Beləliklə, maksimumu permutasiyanın maksimumundan kiçik olan seqmentlərin ümumi sayı:

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

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

Komplekslik $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)

Python