Minimum Artan Dairə#12253

Minimum Artan Dairə (Həll təhlili)

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

Həll

Biz yalnız hansı indeksləri saxlayırıq (0 əməliyyat) və hansını bir anda düzəldirik (1 əməliyyat) ilə maraqlanırıq. $a_{i}$ a_i üzərində bir əməliyyat $a_{i} \leftarrow (a_{i} + t) mod k$ a_i\leftarrow(a_i+t)\bmod k ilə $t \geq m$ t\ge m icazə verir, və biz $k$ -nın istənilən katını əlavə edə bildiyimiz üçün, bir əməliyyat $a_{i}$ a_i-ni $[0, k - 1]$ [0,k-1] aralığında istənilən dəyərə təyin edə bilər. Beləliklə:

saxlanılan indeks: dəyər $a_{i}$ a_i olaraq qalır,
dəyişdirilən indeks: dəyər $[0, k - 1]$ [0,k-1] aralığında istənilən dəyərə çevrilir.

Vacib məhdudiyyət:

Əgər biz $a_{i} \geq k$ a_i\ge k olan bəzi indeksləri saxlayırıqsa, o zaman onun sağındakı hər şey də saxlanmalı və artıq azalmamalıdır; əks halda, dəyişdirilmiş bir dəyər ( $\leq k - 1$ \le k-1) $\geq k$ -dan sonra yerləşməli olacaq ki, bu da sıralamanı pozar. Beləliklə, $a_{i} \geq k$ a_i\ge k olan bir indeks yalnız $a [i .. n]$ ardıcıllığı artıq azalmırsa saxlanmağa uyğun hesab olunur.
Əgər $a_{i} < k$ a_i<k-dirsə, həmişə saxlanmağa uyğun hesab olunur (dəyişdirilmiş qonşular $[0, k - 1]$ [0,k-1] aralığında seçilə bilər).

Biz saxlanılan indekslərin sayını maksimuma çatdırmaq istəyirik; qalanları dəyişdirilir. Hər hansı saxlanılan dəst dəyər baxımından azalmamalıdır. Buna görə də, biz uyğun mövqelər üzərində LIS (azalmayan variant, yəni, $\leq$ -versiyası) götürürük:

uy g ˘ un (i) : (a [i] < k) və ya (suf [i] = 0),

\text{uyğun}(i):\quad (a[i]<k)\ \ \text{və ya}\ \ (\text{suf}[i]=0),

burada $suf [i]$ $a [i .. n]$ -də azalmaları sayır. Cavab:

ops_{m i n} = n - LIS .

\text{ops}_{\min}=n-\text{LIS}.

Niyə: saxlanılan elementlər azalmayan alt ardıcıllığı təşkil edir (biz onları heç vaxt dəyişmirik), və hər hansı digər yeri $[0, k - 1]$ [0,k-1] aralığında dəyişdirilmiş dəyərlərlə doldurmaq mümkündür ki, sıralama saxlanılsın. Əgər saxlanılan $\geq k$ görünürsə, uyğunluq onun arxasında dəyişdirilmiş girişlərin olmadığı təmiz azalmayan ardıcıllığı təmin edir.

Hesablama mürəkkəbliyi $O (n lo g n)$ \mathcal{O}(n \log n)-dir.

def solve():
    n,m,k=map(int,input().split())
    a=list(map(int,input().split()))
    suf=[0]*n
    for i in range(n-2,-1,-1):
        suf[i]=suf[i+1]+(a[i]>a[i+1])
    INF=10**18
    dp=[INF]*(n+1)
    dp[0]=-INF
    lis=0
    for i in range(n):
        if a[i]<k or suf[i]==0:
            l,r,b=1,n,0
            while l<=r:
                mid=(l+r)//2
                if dp[mid]<=a[i]:
                    b=mid;l=mid+1
                else:
                    r=mid-1
            if a[i]<dp[b+1]: dp[b+1]=a[i]
            if b+1>lis: lis=b+1
    print(n-lis)

for _ in range(int(input())):
    solve()

Python