「\(f(x) =\) 元の整数が \(x\) であったときの現時点の値」という関数を考えると、いかなる時点でもこの関数は（\(-10^9 \le x \le 10^9\) の範囲では）以下のいずれかの形をしています。

• \(f(x) = max(L, min(x, R))\)
• \(f(x) = max(L, min(-x, R))\)

したがって、「\(x\) にかかる係数（\(1\) または \(-1\)）」「\(L,R\)」のみを計算していくことで、\(O(N + Q)\) でこの問題を解くことが出来ます。

解答例：

#include<bits/stdc++.h>
using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;

  int l = -1e9, r = 1e9, sign = 1;
  for (int i = 0; i < N; i++) {
    string s; int p;
    cin >> s >> p;
    if (s == "NEGATE") {
      l = -l;
      r = -r;
      swap(l,r);
      sign = -sign;
    } else if (s == "CHMIN") {
      l = min(l, p);
      r = min(r, p);
    } else {
      l = max(l, p);
      r = max(r, p);
    }
  }

  for (int i = 0; i < Q; i++) {
    int q;
    cin >> q;
    int ans = q*sign;
    ans = max(ans, l);
    ans = min(ans, r);
    cout << ans << '\n';
  }
  return 0;
}