AtCoder Beginner Contest 196 E.Filters

题目链接

Problem Statement

Given are integer sequences $A=(a_1,a_2,…,a_N)$, $T=(t_1,t_2,…,t_N)$, and $X=(x_1,x_2,…,x_Q)$.
Let us define $N$ functions $f_1(x),f_2(x),…,f_N(x)$
as follows:

$$f_i(x)= \begin{cases} x+a_i\ (t_i=1)\\ max(x,a_i)\ (t_i=2)\\ min(x,a_i)\ (t_i=3) \end{cases}$$

Sample Input 1

3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

Sample Output 1

0
0
5
10
10

利用几何作图发现上述三个操作总是会形成如下的图形：

那么我们只需要维护三个变量：$low$ 下界，$high$ 上界和 $add$ 加数即可，AC代码如下:

n = int(input())
low, high, add = -10 ** 18, 10 ** 18, 0
for _ in range(n):
    a, t = map(int, input().split())
    if t == 1:
        low += a
        high += a
        add += a
    elif t == 2:
        low = max(low, a)
        high = max(high, a)
    elif t == 3:
        low = min(low, a)
        high = min(high, a)
q = int(input())
s = input()
list = [int(_) for _ in s.split()]
for x in list:
    print(min(high, max(low, x + add)))