Rivalries (Codeforces 1852E)
Tags: Greedy, data structures

Ntarsis has an array $$$a$$$ of length $$$n$$$.The power of a subarray $$$a_l \dots a_r$$$ ($$$1 \leq l \leq r \leq n$$$) is defined as:   The largest value $$$x$$$ such that $$$a_l \dots a_r$$$ contains $$$x$$$ and neither $$$a_1 \dots a_{l-1}$$$ nor $$$a_{r+1} \dots a_n$$$ contains $$$x$$$.  If no such $$$x$$$ exists, the power is $$$0$$$. Call an array $$$b$$$ a rival to $$$a$$$ if the following holds:   The length of both $$$a$$$ and $$$b$$$ are equal to some $$$n$$$.  Over all $$$l, r$$$ where $$$1 \leq l \leq r \leq n$$$, the power of $$$a_l \dots a_r$$$ equals the power of $$$b_l \dots b_r$$$.  The elements of $$$b$$$ are positive. Ntarsis wants you to find a rival $$$b$$$ to $$$a$$$ such that the sum of $$$b_i$$$ over $$$1 \leq i \leq n$$$ is maximized. Help him with this task!

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.The first line of each test case has a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ — a valid rival to $$$a$$$ such that $$$b_1 + b_2 + \cdots + b_n$$$ is maximal. If there exist multiple rivals with the maximum sum, output any of them.

Note: For the first test case, one rival with the maximal sum is $$$[2, 4, 2, 3, 3]$$$.$$$[2, 4, 2, 3, 3]$$$ can be shown to be a rival to $$$[1, 4, 1, 3, 3]$$$.All possible subarrays of $$$a$$$ and $$$b$$$ and their corresponding powers are listed below:   The power of $$$a[1:1] = [1] = 0$$$, the power of $$$b[1:1] = [2] = 0$$$.  The power of $$$a[1:2] = [1, 4] = 4$$$, the power of $$$b[1:2] = [2, 4] = 4$$$.  The power of $$$a[1:3] = [1, 4, 1] = 4$$$, the power of $$$b[1:3] = [2, 4, 2] = 4$$$.  The power of $$$a[1:4] = [1, 4, 1, 3] = 4$$$, the power of $$$b[1:4] = [2, 4, 2, 3] = 4$$$.  The power of $$$a[1:5] = [1, 4, 1, 3, 3] = 4$$$, the power of $$$b[1:5] = [2, 4, 2, 3, 3] = 4$$$.  The power of $$$a[2:2] = [4] = 4$$$, the power of $$$b[2:2] = [4] = 4$$$.  The power of $$$a[2:3] = [4, 1] = 4$$$, the power of $$$b[2:3] = [4, 2] = 4$$$.  The power of $$$a[2:4] = [4, 1, 3] = 4$$$, the power of $$$b[2:4] = [4, 2, 3] = 4$$$.  The power of $$$a[2:5] = [4, 1, 3, 3] = 4$$$, the power of $$$b[2:5] = [4, 2, 3, 3] = 4$$$.  The power of $$$a[3:3] = [1] = 0$$$, the power of $$$b[3:3] = [2] = 0$$$.  The power of $$$a[3:4] = [1, 3] = 0$$$, the power of $$$b[3:4] = [2, 3] = 0$$$.  The power of $$$a[3:5] = [1, 3, 3] = 3$$$, the power of $$$b[3:5] = [2, 3, 3] = 3$$$.  The power of $$$a[4:4] = [3] = 0$$$, the power of $$$b[4:4] = [3] = 0$$$.  The power of $$$a[4:5] = [3, 3] = 3$$$, the power of $$$b[4:5] = [3, 3] = 3$$$.  The power of $$$a[5:5] = [3] = 0$$$, the power of $$$b[5:5] = [3] = 0$$$. It can be shown there exists no rival with a greater sum than $$$2 + 4 + 2 + 3 + 3 = 14$$$.

Sample Inputs:
7
5
1 4 1 3 3
5
1 4 1 8 8
5
2 1 1 1 2
8
3 2 3 5 2 2 5 3
8
1 1 1 1 4 3 3 3
10
1 9 5 9 8 1 5 8 9 1
16
1 1 1 1 5 5 5 5 9 9 9 9 7 7 7 7

Sample Outputs:
2 4 2 3 3
3 4 3 8 8
2 1 2 1 2
4 2 4 5 5 2 5 4
1 2 2 1 4 3 2 3
7 9 5 9 8 9 5 8 9 7
1 8 8 1 5 8 8 5 9 9 9 9 7 8 8 7

Solution (Python):
import sys
input = sys.stdin.readline
out = []

class SegmentTree:

    def __init__(self, data, default=0, func=max):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
out = []
H = int(input())
for L in range(H):
    n = int(input())
    a = list(map(int, input().split()))
    b = a + [max(1, v - 1) for v in a]
    b = sorted(set(b))
    MX = len(b)
    b.append(float('inf'))
    comp = {}
    for i in range(MX - 1, -1, -1):
        comp[b[i]] = i
    a = [comp[v] for v in a]
    op = [-1] * MX
    cl = [-1] * MX
    for i in range(n):
        cl[a[i]] = i
        if op[a[i]] == -1:
            op[a[i]] = i
    seg = SegmentTree([0] * MX, default=-1)
    imp = [0] * n
    rem = SegmentTree(list(range(n)), default=-1)
    ct = n
    tot = 0
    power = [0] * MX
    for i in range(n):
        if i == cl[a[i]]:
            if seg.query(a[i], MX) <= op[a[i]]:
                seg[a[i]] = op[a[i]]
                power[a[i]] = 1
                imp[op[a[i]]] = 1
                imp[cl[a[i]]] = 1
                if rem[op[a[i]]] != -1:
                    rem[op[a[i]]] = -1
                    ct -= 1
                    tot += b[a[i]]
                if rem[cl[a[i]]] != -1:
                    rem[cl[a[i]]] = -1
                    ct -= 1
                    tot += b[a[i]]
    taken = SegmentTree([MX] * n, default=MX, func=min)
    poss = []
    check = []
    for i in range(MX - 1, -1, -1):
        if power[i] == 0:
            while check:
                (l, r) = check.pop()
                pen = 0
                if rem.query(0, l) == -1:
                    prev = taken.query(0, l)
                    pen += b[prev] - b[i]
                if rem.query(r, n) == -1:
                    prev = taken.query(r, n)
                    pen += b[prev] - b[i]
                poss.append((ct * b[i] + tot - pen, i, l, r))
        else:
            ind = rem.query(op[i], cl[i])
            while ind != -1:
                tot += b[i]
                rem[ind] = -1
                taken[ind] = i
                ct -= 1
                ind = rem.query(op[i], cl[i])
            check.append((op[i], cl[i]))
    if ct == 0:
        poss.append((tot, MX, -1, -1))
    ol = a
    (val, a, l, r) = max(poss)
    tt = taken.data[taken._size:taken._size + taken._len]
    rr = rem.data[rem._size:rem._size + rem._len]
    if a < MX:
        u = 0
        for i in range(l):
            if tt[i] < a or rr[i] != -1:
                u = 1
                tt[i] = a
        if u == 0:
            want = min(tt[:l])
            assert want < MX
            for i in range(l):
                if tt[i] == want:
                    tt[i] = a
                    break
        u = 0
        for i in range(r, n):
            if tt[i] < a or rr[i] != -1:
                u = 1
                tt[i] = a
        if u == 0:
            want = min(tt[r:n])
            assert want < MX
            for i in range(r, n):
                if tt[i] == want:
                    tt[i] = a
                    break
    for i in range(n):
        if tt[i] == MX:
            assert imp[i]
            tt[i] = ol[i]
    zz = [b[v] for v in tt]
    assert sum(zz) == val
    out.append(' '.join(map(str, zz)))
print('\n'.join(out))

Solution (Python):
import sys
input = sys.stdin.readline
out = []

class SegmentTree:

    def __init__(self, data, default=0, func=max):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
out = []
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = a + [max(1, v - 1) for v in a]
    b = sorted(set(b))
    MX = len(b)
    b.append(float('inf'))
    comp = {}
    for i in range(MX - 1, -1, -1):
        comp[b[i]] = i
    a = [comp[v] for v in a]
    op = [-1] * MX
    cl = [-1] * MX
    for i in range(n):
        cl[a[i]] = i
        if op[a[i]] == -1:
            op[a[i]] = i
    seg = SegmentTree([0] * MX, default=-1)
    imp = [0] * n
    rem = SegmentTree(list(range(n)), default=-1)
    ct = n
    tot = 0
    power = [0] * MX
    for i in range(n):
        if i == cl[a[i]]:
            if seg.query(a[i], MX) <= op[a[i]]:
                seg[a[i]] = op[a[i]]
                power[a[i]] = 1
                imp[op[a[i]]] = 1
                imp[cl[a[i]]] = 1
                if rem[op[a[i]]] != -1:
                    rem[op[a[i]]] = -1
                    ct -= 1
                    tot += b[a[i]]
                if rem[cl[a[i]]] != -1:
                    rem[cl[a[i]]] = -1
                    ct -= 1
                    tot += b[a[i]]
    taken = SegmentTree([MX] * n, default=MX, func=min)
    poss = []
    check = []
    for i in range(MX - 1, -1, -1):
        if power[i] == 0:
            while check:
                (l, r) = check.pop()
                pen = 0
                if rem.query(0, l) == -1:
                    prev = taken.query(0, l)
                    pen += b[prev] - b[i]
                if rem.query(r, n) == -1:
                    prev = taken.query(r, n)
                    pen += b[prev] - b[i]
                poss.append((ct * b[i] + tot - pen, i, l, r))
        else:
            ind = rem.query(op[i], cl[i])
            while ind != -1:
                tot += b[i]
                rem[ind] = -1
                taken[ind] = i
                ct -= 1
                ind = rem.query(op[i], cl[i])
            check.append((op[i], cl[i]))
    if ct == 0:
        poss.append((tot, MX, -1, -1))
    ol = a
    (val, a, l, r) = max(poss)
    tt = taken.data[taken._size:taken._size + taken._len]
    rr = rem.data[rem._size:rem._size + rem._len]
    if a < MX:
        u = 0
        for i in range(l):
            if tt[i] < a or rr[i] != -1:
                u = 1
                tt[i] = a
        if u == 0:
            want = min(tt[:l])
            assert want < MX
            for i in range(l):
                if tt[i] == want:
                    tt[i] = a
                    break
        u = 0
        for i in range(r, n):
            if tt[i] < a or rr[i] != -1:
                u = 1
                tt[i] = a
        if u == 0:
            want = min(tt[r:n])
            assert want < MX
            for i in range(r, n):
                if tt[i] == want:
                    tt[i] = a
                    break
    for i in range(n):
        if tt[i] == MX:
            assert imp[i]
            tt[i] = ol[i]
    zz = [b[v] for v in tt]
    assert sum(zz) == val
    out.append(' '.join(map(str, zz)))
print('\n'.join(out))

Solution (Python):
import sys
input = sys.stdin.readline
out = []

class SegmentTree:

    def __init__(self, data, default=0, func=max):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """"""
        start += self._size
        stop += self._size
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
        return self._func(res_left, res_right)

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
out = []
H = int(input())
for L in range(H):
    n = int(input())
    a = list(map(int, input().split()))
    b = a + [max(1, v - 1) for v in a]
    b = sorted(set(b))
    MX = len(b)
    b.append(float('inf'))
    comp = {}
    for i in range(MX - 1, -1, -1):
        comp[b[i]] = i
    a = [comp[v] for v in a]
    op = [-1] * MX
    cl = [-1] * MX
    for i in range(n):
        cl[a[i]] = i
        if op[a[i]] == -1:
            op[a[i]] = i
    seg = SegmentTree([0] * MX, default=-1)
    imp = [0] * n
    rem = SegmentTree(list(range(n)), default=-1)
    ct = n
    tot = 0
    power = [0] * MX
    for i in range(n):
        if i == cl[a[i]]:
            if seg.query(a[i], MX) <= op[a[i]]:
                seg[a[i]] = op[a[i]]
                power[a[i]] = 1
                imp[op[a[i]]] = 1
                imp[cl[a[i]]] = 1
                if rem[op[a[i]]] != -1:
                    rem[op[a[i]]] = -1
                    ct -= 1
                    tot += b[a[i]]
                if rem[cl[a[i]]] != -1:
                    rem[cl[a[i]]] = -1
                    ct -= 1
                    tot += b[a[i]]
    taken = SegmentTree([MX] * n, default=MX, func=min)
    poss = []
    check = []
    for i in range(MX - 1, -1, -1):
        if power[i] == 0:
            while check:
                (l, r) = check.pop()
                pen = 0
                if rem.query(0, l) == -1:
                    prev = taken.query(0, l)
                    pen += b[prev] - b[i]
                if rem.query(r, n) == -1:
                    prev = taken.query(r, n)
                    pen += b[prev] - b[i]
                poss.append((ct * b[i] + tot - pen, i, l, r))
        else:
            ind = rem.query(op[i], cl[i])
            while ind != -1:
                tot += b[i]
                rem[ind] = -1
                taken[ind] = i
                ct -= 1
                ind = rem.query(op[i], cl[i])
            check.append((op[i], cl[i]))
    if ct == 0:
        poss.append((tot, MX, -1, -1))
    ol = a
    (val, a, l, r) = max(poss)
    tt = taken.data[taken._size:taken._size + taken._len]
    rr = rem.data[rem._size:rem._size + rem._len]
    if a < MX:
        u = 0
        for i in range(l):
            if tt[i] < a or rr[i] != -1:
                u = 1
                tt[i] = a
        if u == 0:
            want = min(tt[:l])
            assert want < MX
            for i in range(l):
                if tt[i] == want:
                    tt[i] = a
                    break
        u = 0
        for i in range(r, n):
            if tt[i] < a or rr[i] != -1:
                u = 1
                tt[i] = a
        if u == 0:
            want = min(tt[r:n])
            assert want < MX
            for i in range(r, n):
                if tt[i] == want:
                    tt[i] = a
                    break
    for i in range(n):
        if tt[i] == MX:
            assert imp[i]
            tt[i] = ol[i]
    zz = [b[v] for v in tt]
    assert sum(zz) == val
    out.append(' '.join(map(str, zz)))
print('\n'.join(out))