Hot is Cold (Codeforces 1146E)
Tags: Implement, divide and conquer

You are given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$.You will perform $$$q$$$ operations. In the $$$i$$$-th operation, you have a symbol $$$s_i$$$ which is either "<" or ">" and a number $$$x_i$$$.You make a new array $$$b$$$ such that $$$b_j = -a_j$$$ if $$$a_j s_i x_i$$$ and $$$b_j = a_j$$$ otherwise (i.e. if $$$s_i$$$ is '>', then all $$$a_j > x_i$$$ will be flipped). After doing all these replacements, $$$a$$$ is set to be $$$b$$$.You want to know what your final array looks like after all operations.

Input: The first line contains two integers $$$n,q$$$ ($$$1 \leq n,q \leq 10^5$$$) — the number of integers and the number of queries.The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^5 \leq a_i \leq 10^5$$$) — the numbers.Each of the next $$$q$$$ lines contains a character and an integer $$$s_i, x_i$$$. ($$$s_i \in \{<, >\}, -10^5 \leq x_i \leq 10^5$$$) – the queries.

Output: Print $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ representing the array after all operations.

Note: In the first example, the array goes through the following changes:   Initial: $$$[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]$$$  $$$> 2$$$: $$$[-5, -4, -3, -2, -1, 0, 1, 2, -3, -4, -5]$$$  $$$> -4$$$: $$$[-5, -4, 3, 2, 1, 0, -1, -2, 3, -4, -5]$$$  $$$< 5$$$: $$$[5, 4, -3, -2, -1, 0, 1, 2, -3, 4, 5]$$$ 

Sample Inputs:
11 3
-5 -4 -3 -2 -1 0 1 2 3 4 5
> 2
> -4
< 5

5 5
0 1 -2 -1 2
< -2
< -1
< 0
< 1
< 2

Sample Outputs:
5 4 -3 -2 -1 0 1 2 -3 4 5

0 -1 2 -1 2

Solution (Python):
import sys
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
Sign = [0] * (3 + 10 ** 5)
SX = [tuple(sys.stdin.readline().split()) for _ in range(Q)]
mini = 3 + 10 ** 5
Sign = [0] * (3 + 10 ** 5)
keep = 1
for (s, x) in SX[::-1]:
    x = int(x)
    ax = abs(x) + int((s == '>') ^ (x < 0))
    sin = 1 if s == '<' else -1
    if mini > ax:
        t = sin * keep
        for i in range(mini - 1, ax - 1, -1):
            Sign[i] = t
        mini = ax
    keep *= (2 * (s == '>') - 1) * (2 * (0 < x) - 1)
Ans = [None] * N
for (i, a) in enumerate(A):
    s = Sign[abs(a)]
    if s == 0:
        s = (2 * (a > 0) - 1) * keep
    Ans[i] = s * abs(a)
print(*Ans)

Solution (Python):
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
swaps = [0] * q
for i in range(q):
    b = input().split()
    b[1] = int(b[1])
    out = 1 if b[0] == '<' and b[1] <= 0 or (b[0] == '>' and b[1] >= 0) else 0
    split = b[1] + 0.5 if b[0] == '>' else b[1] - 0.5
    sign = 1 if split > 0 else -1
    split = abs(split)
    swaps[i] = (split, sign, out)
sml = 10 ** 5 + 0.5
zeros = 0
for i in range(q):
    sml = min(swaps[i][0], sml)
    zeros += 1 - swaps[i][2]
zeros %= 2
arr = [0] * 100001
big = 100000.5
flips = 1
for i in range(q):
    if swaps[-1 - i][0] < big:
        if swaps[-1 - i][2] == 1:
            for j in range(int(swaps[-1 - i][0] + 0.5), int(big + 0.5)):
                arr[j] = -swaps[-i - 1][1] * flips
        else:
            for j in range(int(swaps[-1 - i][0] + 0.5), int(big + 0.5)):
                arr[j] = swaps[-i - 1][1] * flips
        big = swaps[-1 - i][0]
    if swaps[-1 - i][2] == 0:
        flips = -flips

def func(k):
    if abs(k) < sml:
        return k if zeros == 0 else -k
    else:
        return arr[abs(k)] * abs(k)
print(' '.join([str(func(guy)) for guy in a]))

Solution (Python):
import sys
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
Sign = [0] * (3 + 10 ** 5)
SX = [tuple(sys.stdin.readline().split()) for _ in range(Q)]
mini = 3 + 10 ** 5
Sign = [0] * (3 + 10 ** 5)
keep = 1
for (s, x) in SX[::-1]:
    x = int(x)
    ax = abs(x) + int((s == '>') ^ (x < 0))
    sin = 1 if s == '<' else -1
    if mini > ax:
        t = sin * keep
        for i in range(mini - 1, ax - 1, -1):
            Sign[i] = t
        mini = ax
    keep *= (2 * (s == '>') - 1) * (2 * (0 < x) - 1)
Ans = [None] * N
for (i, a) in enumerate(A):
    s = Sign[abs(a)]
    if s == 0:
        s = (2 * (a > 0) - 1) * keep
    Ans[i] = s * abs(a)
print(*Ans)