Мінімальний зростаючий цикл#12253

Мінімальний зростаючий цикл (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Нам важливо лише те, які індекси ми зберігаємо (0 операцій) і які ми виправляємо за один раз (1 операція). Одна операція над $a_{i}$ a_i дозволяє $a_{i} \leftarrow (a_{i} + t) mod k$ a_i\leftarrow(a_i+t)\bmod k з $t \geq m$ t\ge m, і оскільки ми можемо додати будь-яке кратне $k$ зверху, одна операція може встановити $a_{i}$ a_i на будь-яке значення в $[0, k - 1]$ [0,k-1]. Отже:

збережений індекс: значення залишається $a_{i}$ a_i,
змінений індекс: значення стає будь-яким у $[0, k - 1]$ [0,k-1].

Ключове обмеження:

Якщо ми зберігаємо деяке $a_{i} \geq k$ a_i\ge k, тоді все праворуч від нього також повинно бути збережено і вже бути незменшуваним; в іншому випадку змінене значення ( $\leq k - 1$ \le k-1) повинно бути після $\geq k$ , що може порушити порядок. Отже, індекс $i$ з $a_{i} \geq k$ a_i\ge k є придатним для збереження лише якщо суфікс $a [i .. n]$ вже незменшуваний.
Якщо $a_{i} < k$ a_i<k, він завжди є придатним для збереження (змінені сусіди можуть бути вибрані всередині $[0, k - 1]$ [0,k-1] для відповідності).

Ми хочемо максимізувати кількість збережених індексів; решта змінюються. Будь-який збережений набір повинен бути незменшуваним за значенням. Отже, ми беремо LIS (незменшувана варіація, тобто версія $\leq$ ) над потоком придатних позицій:

eligible (i) : (a [i] < k) or (suf [i] = 0),

\text{eligible}(i):\quad (a[i]<k)\ \ \text{or}\ \ (\text{suf}[i]=0),

де $suf [i]$ підраховує спади в $a [i .. n]$ . Відповідь:

ops_{m i n} = n - LIS .

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

Чому: збережені елементи формують незменшувану підпослідовність (ми ніколи їх не змінюємо), і кожне інше місце може бути заповнене зміненими значеннями в межах $[0, k - 1]$ [0,k-1], щоб підтримувати порядок. Якщо збережений $\geq k$ з'являється, придатність забезпечує чистий незменшуваний суфікс без змінених записів після нього.

Складність становить $O (n lo g n)$ \mathcal{O}(n \log n)

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