\(x_1, x_2, \dots, x_Q\) のそれぞれに関数 \(f_1, f_2, \dots, f_N\) を順次適用させていく \(\Theta(NQ)\) の解法は \(NQ\) が最大 \(4 \times 10^{10}\) になるため TLE になります。
そこで、合成関数 \(F(x) = f_N(\dots f_2(f_1(x))\dots)\) がどのような形になるかを考えてみましょう。

\(t_i = 1\) のとき、 \(f_i\) はグラフを上下に移動させる操作、
\(t_i = 2\) のとき、 \(f_i\) は \(a_i\) より小さい部分を \(a_i\) にする操作、
\(t_i = 3\) のとき、 \(f_i\) は \(a_i\) より大きい部分を \(a_i\) にする操作であるので、
これらを組み合わせてできる関数は下の図のような形をしている、つまり、ある数 \(a, b, c\) が存在して \(F(x) = \min(c, \max(b, x + a))\) と表現できるだろうと予想できます。

これは以下のように証明できます。

\(t_i = 1\) のとき、\(f_i(x) = \min(\infty, \max(-\infty, x + a_i))\) 、
\(t_i = 2\) のとき、\(f_i(x) = \min(\infty, \max(a_i, x + 0))\) 、
\(t_i = 3\) のとき、\(f_i(x) = \min(a_i, \max(-\infty, x + 0))\) と、\(f_i(x)\) を \(\min(c, \max(b, x + a))\) の形で表現できます。

また、\(f(x) = \min(c_1, \max(b_1, x + a_1)), g(x) = \min(c_2, \max(b_2, x + a_2))\) としたとき、これらの合成関数 \(g(f(x))\) は、

\[ \begin{aligned} g(f(x)) &= \min(c_2, \max(b_2, \min(c_1, \max(b_1, x + a_1)) + a_2))\\ &= \min(c_2, \max(b_2, \min(c_1 + a_2, \max(b_1 + a_2, x + a_1 + a_2))))\\ &= \min(\min(c_2, \max(b_2, c_1 + a_2)), \max(\max(b_2, \min(c_1 + a_2, b_1 + a_2)), x + (a_1 + a_2)))\\ \end{aligned} \]

と、\(\min(c, \max(b, x + a))\) の形で表現できます。

\(F(x)\) は \(f_1, f_2, …, f_N\) の合成でできているので、\(\min(c, \max(b, x + a))\) の形で表現できることが証明できました。

次は、\(F(x) = \min(c, \max(b, x + a))\) と表したときの \(a, b, c\) の値を求めましょう。
これは、上の合成規則 \(g(f(x))\) に従って \(f_1, f_2, \dots, f_N\) を合成していけば計算できます。

\(a, b, c\) の値がわかれば \(F(x)\) の計算は \(O(1)\) で行えるので、全体で \(O(N + Q)\) でこの問題を解くことができました。

追記

\(f(x) = \min(c_1, \max(b_1, x + a_1))\) と \(g(x) = \min(c_2, \max(b_2, x + a_2))\) を合成するより、\(f(x)\) と各操作を合成してみて \(\min(c, \max(b, x + a))\) の形になることを示す方が簡単です。

\(\text{clamp}(x, l, r) = \min(r, \max(l, x))\) と定義すると、

\[ \begin{aligned} F(x) + a &= \text{clamp}(x + (a + c), a + l, a + r)\\ \min(F(x), a) &= \text{clamp}(x + c, \min(a, l), \min(a, r))\\ \max(F(x), a) &= \text{clamp}(x + c, \max(a, l), \max(a, r))\\ \end{aligned} \]

となります。

回答例 (C++)

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = numeric_limits<ll>::max() / 4;
void chmin(ll& a, ll b){ if(a > b) a = b; }
void chmax(ll& a, ll b){ if(a < b) a = b; }

int main(){
    ll N;
    cin >> N;
    ll low = -INF, high = INF, add = 0;
    for(ll i = 0; i < N; i++){
        ll A, T;
        cin >> A >> T;
        if(T == 1){
            low += A;
            high += A;
            add += A;
        }
        else if(T == 2){
            chmax(low, A);
            chmax(high, A);
        }
        else{
            chmin(low, A);
            chmin(high, A);
        }
    }
    ll Q;
    cin >> Q;
    for(ll i = 0; i < Q; i++){
        ll x;
        cin >> x;
        cout << clamp(x + add, low, high) << '\n';
    }
}

回答例 (Python)

N = int(input())
low = -1 << 60
high = 1 << 60
add = 0
for i in range(N):
    A, T = map(int, input().split())
    if T == 1:
        low += A
        high += A
        add += A
    elif T == 2:
        if low < A:
            low = A
        if high < A:
            high = A
    else:
        if low > A:
            low = A
        if high > A:
            high = A
input()
for x in map(int, input().split()):
    print(min(high, max(low, x + add)))