Greedy Subsequences (Codeforces 1132G)
Tags: DP, trees

For some array $$$c$$$, let's denote a greedy subsequence as a sequence of indices $$$p_1$$$, $$$p_2$$$, ..., $$$p_l$$$ such that $$$1 \le p_1 < p_2 < \dots < p_l \le |c|$$$, and for each $$$i \in [1, l - 1]$$$, $$$p_{i + 1}$$$ is the minimum number such that $$$p_{i + 1} > p_i$$$ and $$$c[p_{i + 1}] > c[p_i]$$$.You are given an array $$$a_1, a_2, \dots, a_n$$$. For each its subsegment of length $$$k$$$, calculate the length of its longest greedy subsequence.

Input: The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^6$$$) — the length of array $$$a$$$ and the length of subsegments.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — array $$$a$$$.

Output: Print $$$n - k + 1$$$ integers — the maximum lengths of greedy subsequences of each subsegment having length $$$k$$$. The first number should correspond to subsegment $$$a[1..k]$$$, the second — to subsegment $$$a[2..k + 1]$$$, and so on.

Note: In the first example:   $$$[1, 5, 2, 5]$$$ — the longest greedy subsequences are $$$1, 2$$$ ($$$[c_1, c_2] = [1, 5]$$$) or $$$3, 4$$$ ($$$[c_3, c_4] = [2, 5]$$$).  $$$[5, 2, 5, 3]$$$ — the sequence is $$$2, 3$$$ ($$$[c_2, c_3] = [2, 5]$$$).  $$$[2, 5, 3, 6]$$$ — the sequence is $$$1, 2, 4$$$ ($$$[c_1, c_2, c_4] = [2, 5, 6]$$$). In the second example:   $$$[4, 5, 2, 5, 3, 6]$$$ — the longest greedy subsequences are $$$1, 2, 6$$$ ($$$[c_1, c_2, c_6] = [4, 5, 6]$$$) or $$$3, 4, 6$$$ ($$$[c_3, c_4, c_6] = [2, 5, 6]$$$).  $$$[5, 2, 5, 3, 6, 6]$$$ — the subsequence is $$$2, 3, 5$$$ ($$$[c_2, c_3, c_5] = [2, 5, 6]$$$). 

Sample Inputs:
6 4
1 5 2 5 3 6

7 6
4 5 2 5 3 6 6

Sample Outputs:
2 2 3

3 3

Solution (Python):
from array import array
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m, x):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(2, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def euler_tour():
    s = []
    s.append(n)
    now = list(s0)
    t = 1
    (t1, t2) = ([-1] * (n + 1), [-1] * (n + 1))
    while s:
        i = s[-1]
        if t1[i] == -1:
            t1[i] = t
        if now[i] == s0[i + 1]:
            t2[i] = t
            t += 1
            s.pop()
        else:
            s.append(G[now[i]])
            now[i] += 1
    return (t1, t2)

def update(l, r, s):
    update0(l, -s)
    update0(r + 1, s)
    return

def update0(r, s):
    (u, v) = (l1, 1)
    for _ in range(l0 + 1):
        if r & u:
            lazy[v] += s
            if lazy[v]:
                tree[v] += lazy[v]
                if v < l1:
                    lazy[v << 1] += lazy[v]
                    lazy[v << 1 ^ 1] += lazy[v]
                lazy[v] = 0
            r ^= u
            v ^= 1
        if lazy[v]:
            tree[v] += lazy[v]
            if v < l1:
                lazy[v << 1] += lazy[v]
                lazy[v << 1 ^ 1] += lazy[v]
            lazy[v] = 0
        if not r:
            break
        u >>= 1
        v <<= 1
    while v:
        if v < l1:
            (j, k) = (v << 1, v << 1 ^ 1)
            tree[v] = max(tree[j] + lazy[j], tree[k] + lazy[k])
        v = v ^ 1 if v & 1 else v >> 1
    return
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = [0] * (2 * n)
l = 0
st = []
for i in range(n):
    ai = a[i]
    while st and a[st[-1]] < ai:
        j = st.pop()
        (x[l], x[l + 1]) = (i, j)
        l += 2
    st.append(i)
for i in st:
    (x[l], x[l + 1]) = (n, i)
    l += 2
(G, s0) = make_graph(n + 1, n, x)
(t1, t2) = euler_tour()
l0 = 20
l1 = pow(2, l0)
l2 = 2 * l1
(tree, lazy) = (array('i', [0] * l2), array('i', [0] * l2))
for i in range(k):
    tree[t1[i] + l1] += 1
    tree[t2[i] + 1 + l1] -= 1
for i in range(l1 + 1, l2):
    tree[i] += tree[i - 1]
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
ans = array('i', [0] * (n - k + 1))
for i in range(k, n):
    ans0 = tree[1]
    ans[i - k] = ans0
    update(t1[i], t2[i], 1)
    update(t1[i - k], t2[i - k], -1)
ans0 = tree[1]
ans[-1] = ans0
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
from array import array
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m, x):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(2, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def euler_tour():
    s = []
    s.append(n)
    now = list(s0)
    t = 1
    (t1, t2) = ([-1] * (n + 1), [-1] * (n + 1))
    while s:
        i = s[-1]
        if t1[i] == -1:
            t1[i] = t
        if now[i] == s0[i + 1]:
            t2[i] = t
            t += 1
            s.pop()
        else:
            s.append(G[now[i]])
            now[i] += 1
    return (t1, t2)

def update(r, s):
    (u, v) = (l1, 1)
    for _ in range(l0 + 1):
        if r & u:
            lazy[v] += s
            if lazy[v]:
                tree[v] += lazy[v]
                if v < l1:
                    lazy[v << 1] += lazy[v]
                    lazy[v << 1 ^ 1] += lazy[v]
                lazy[v] = 0
            r ^= u
            v ^= 1
        if lazy[v]:
            tree[v] += lazy[v]
            if v < l1:
                lazy[v << 1] += lazy[v]
                lazy[v << 1 ^ 1] += lazy[v]
            lazy[v] = 0
        if not r:
            break
        u >>= 1
        v <<= 1
    while v:
        if v < l1:
            (j, k) = (v << 1, v << 1 ^ 1)
            tree[v] = max(tree[j] + lazy[j], tree[k] + lazy[k])
        v = v ^ 1 if v & 1 else v >> 1
    return
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = [0] * (2 * n)
l = 0
st = []
for i in range(n):
    ai = a[i]
    while st and a[st[-1]] < ai:
        j = st.pop()
        (x[l], x[l + 1]) = (i, j)
        l += 2
    st.append(i)
for i in st:
    (x[l], x[l + 1]) = (n, i)
    l += 2
(G, s0) = make_graph(n + 1, n, x)
(t1, t2) = euler_tour()
l0 = 20
l1 = pow(2, l0)
l2 = 2 * l1
(tree, lazy) = (array('i', [0] * l2), array('i', [0] * l2))
for i in range(k):
    tree[t1[i] + l1] += 1
    tree[t2[i] + 1 + l1] -= 1
for i in range(l1 + 1, l2):
    tree[i] += tree[i - 1]
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
ans = array('i', [0] * (n - k + 1))
for i in range(k, n):
    ans0 = tree[1]
    ans[i - k] = ans0
    update(t2[i] + 1, 1)
    update(t2[i - k] + 1, -1)
    update(t1[i], -1)
    update(t1[i - k], 1)
ans0 = tree[1]
ans[-1] = ans0
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
from array import array
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m, x):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(2, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def euler_tour():
    s = []
    s.append(n)
    now = list(s0)
    t = 1
    (t1, t2) = ([-1] * (n + 1), [-1] * (n + 1))
    while s:
        i = s[-1]
        if t1[i] == -1:
            t1[i] = t
        if now[i] == s0[i + 1]:
            t2[i] = t
            t += 1
            s.pop()
        else:
            s.append(G[now[i]])
            now[i] += 1
    return (t1, t2)

def update(l, r, s):
    update0(l, -s)
    update0(r + 1, s)
    return

def update0(r, s):
    (u, v) = (l1, 1)
    for _ in range(l0 + 1):
        if r & u:
            lazy[v] += s
            if lazy[v]:
                tree[v] += lazy[v]
                if v < l1:
                    lazy[v << 1] += lazy[v]
                    lazy[v << 1 ^ 1] += lazy[v]
                lazy[v] = 0
            r ^= u
            v ^= 1
        if lazy[v]:
            tree[v] += lazy[v]
            if v < l1:
                lazy[v << 1] += lazy[v]
                lazy[v << 1 ^ 1] += lazy[v]
            lazy[v] = 0
        if not r:
            break
        u >>= 1
        v <<= 1
    while v:
        if v < l1:
            (j, k) = (v << 1, v << 1 ^ 1)
            tree[v] = max(tree[j] + lazy[j], tree[k] + lazy[k])
        v = v ^ 1 if v & 1 else v >> 1
    return
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = [0] * (2 * n)
l = 0
st = []
for i in range(n):
    ai = a[i]
    while st and a[st[-1]] < ai:
        j = st.pop()
        (x[l], x[l + 1]) = (i, j)
        l += 2
    st.append(i)
for i in st:
    (x[l], x[l + 1]) = (n, i)
    l += 2
(G, s0) = make_graph(n + 1, n, x)
(t1, t2) = euler_tour()
l0 = 20
l1 = pow(2, l0)
l2 = 2 * l1
(tree, lazy) = (array('i', [0] * l2), array('i', [0] * l2))
for i in range(k):
    tree[t1[i] + l1] += 1
    tree[t2[i] + 1 + l1] -= 1
for i in range(l1 + 1, l2):
    tree[i] += tree[i - 1]
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
ans = array('i', [0] * (n - k + 1))
for i in range(k, n):
    ans0 = tree[1]
    ans[i - k] = ans0
    update(t1[i], t2[i], 1)
    update(t1[i - k], t2[i - k], -1)
ans0 = tree[1]
ans[-1] = ans0
sys.stdout.write(' '.join(map(str, ans)))