この問題では以下の4つの操作を実装する必要があります：

• 操作1: 結果にaを加算
• 操作2: 結果からaを減算
• 操作3: 結果にaを乗算
• 操作4: 結果にa * Xを加算

これらの操作を効率的に処理するために、線分木を使用します。線分木は区間最大値と最小値、加算の遅延評価タグ、乗算の遅延評価タグ、代入の遅延評価タグ、および操作4用の遅延評価タグを管理します。

木の構築

通常の線分木の構築を行います。一部の初期化については注釈で説明します。

void build(ll p, ll pl, ll pr) {
    addtag[p] = 0; // グローバル変数はデフォルトで0なので、省略可能
    multag[p] = 1; // 乗算タグは1で初期化
    opt4tag[p] = 0;
    modifytag[p] = 0;
    if (pl == pr) {
        maxtree[p] = mintree[p] = a[pl].val;
        return;
    }
    ll mid = (pl + pr) / 2;
    build(ls(p), pl, mid);
    build(rs(p), mid + 1, pr);
    pushup(p);
}

加算タグの更新

通常の加算タグの更新を行います。

void make_addtag(ll p, ll d) {
    addtag[p] += d;
    maxtree[p] += d;
    mintree[p] += d;
}

乗算タグの更新

乗算タグを更新する際には、加算タグも更新する必要があります。

void make_multag(ll p, ll d) {
    addtag[p] *= d;
    multag[p] *= d;
    opt4tag[p] *= d;
    maxtree[p] *= d;
    mintree[p] *= d;
}

操作4のタグの更新

操作4の要件に従ってタグを更新します。

void make_opt4tag(ll p, ll pl, ll pr, ll d) {
    mintree[p] += a[pl].val * d;
    maxtree[p] += a[pr].val * d;
    opt4tag[p] += d;
}

代入タグの更新

すべてのタグを初期状態に戻します。

void make_modifytag(ll p, ll d) {
    addtag[p] = 0;
    multag[p] = 1;
    opt4tag[p] = 0;
    modifytag[p] = d;
    maxtree[p] = d;
    mintree[p] = d;
}

遅延評価の伝播

全ての遅延評価を統合し、順序を注意深く保つことが重要です。

void pushdown(ll p, ll pl, ll pr) {
    ll mid = (pl + pr) / 2;
    if (modifytag[p]) {
        make_modifytag(ls(p), modifytag[p]);
        make_modifytag(rs(p), modifytag[p]);
        modifytag[p] = 0;
    }
    if (multag[p] != 1) {
        make_multag(ls(p), multag[p]);
        make_multag(rs(p), multag[p]);
        multag[p] = 1;
    }
    if (addtag[p]) {
        make_addtag(ls(p), addtag[p]);
        make_addtag(rs(p), addtag[p]);
        addtag[p] = 0;
    }
    if (opt4tag[p]) {
        make_opt4tag(ls(p), pl, mid, opt4tag[p]);
        make_opt4tag(rs(p), mid + 1, pr, opt4tag[p]);
        opt4tag[p] = 0;
    }
}

区間更新

区間の最小値と最大値の更新を行います。

void min_update(ll p, ll pl, ll pr) {
    if (mintree[p] >= r) {
        make_modifytag(p, r);
        return;
    }
    if (maxtree[p] <= r || pl == pr)
        return;
    pushdown(p, pl, pr);
    ll mid = (pl + pr) / 2;
    min_update(ls(p), pl, mid);
    min_update(rs(p), mid + 1, pr);
    pushup(p);
}

void max_update(ll p, ll pl, ll pr) {
    if (maxtree[p] <= l) {
        make_modifytag(p, l);
        return;
    }
    if (mintree[p] >= l || pl == pr)
        return;
    pushdown(p, pl, pr);
    ll mid = (pl + pr) / 2;
    max_update(ls(p), pl, mid);
    max_update(rs(p), mid + 1, pr);
    pushup(p);
}

答えの取得

再帰的に答えを計算します。

void get_ans(ll p, ll pl, ll pr) {
    if (pl == pr) {
        ans[a[pl].idx] = maxtree[p];
        return;
    }
    pushdown(p, pl, pr);
    ll mid = (pl + pr) / 2;
    get_ans(ls(p), pl, mid);
    get_ans(rs(p), mid + 1, pr);
}

完全なコード

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

using ll = long long;

struct node {
    ll val, idx;
    bool operator<(const node &k) const {
        return this->val < k.val;
    }
} a[100005];

ll n, l, r, q;
char ch;

ll x[100005], opt[100005], ans[100005], maxtree[400020], mintree[400020], addtag[400020], multag[400020], opt4tag[400020], modifytag[400020];

ll ls(ll p) {
    return p << 1;
}

ll rs(ll p) {
    return p << 1 | 1;
}

void pushup(ll p) {
    maxtree[p] = max(maxtree[ls(p)], maxtree[rs(p)]);
    mintree[p] = min(mintree[ls(p)], mintree[rs(p)]);
}

void build(ll p, ll pl, ll pr) {
    addtag[p] = 0;
    multag[p] = 1;
    opt4tag[p] = 0;
    modifytag[p] = 0;
    if (pl == pr) {
        maxtree[p] = mintree[p] = a[pl].val;
        return;
    }
    ll mid = (pl + pr) / 2;
    build(ls(p), pl, mid);
    build(rs(p), mid + 1, pr);
    pushup(p);
}

void make_addtag(ll p, ll d) {
    addtag[p] += d;
    maxtree[p] += d;
    mintree[p] += d;
}

void make_multag(ll p, ll d) {
    addtag[p] *= d;
    multag[p] *= d;
    opt4tag[p] *= d;
    maxtree[p] *= d;
    mintree[p] *= d;
}

void make_opt4tag(ll p, ll pl, ll pr, ll d) {
    mintree[p] += a[pl].val * d;
    maxtree[p] += a[pr].val * d;
    opt4tag[p] += d;
}

void make_modifytag(ll p, ll d) {
    addtag[p] = 0;
    multag[p] = 1;
    opt4tag[p] = 0;
    modifytag[p] = d;
    maxtree[p] = d;
    mintree[p] = d;
}

void pushdown(ll p, ll pl, ll pr) {
    ll mid = (pl + pr) / 2;
    if (modifytag[p]) {
        make_modifytag(ls(p), modifytag[p]);
        make_modifytag(rs(p), modifytag[p]);
        modifytag[p] = 0;
    }
    if (multag[p] != 1) {
        make_multag(ls(p), multag[p]);
        make_multag(rs(p), multag[p]);
        multag[p] = 1;
    }
    if (addtag[p]) {
        make_addtag(ls(p), addtag[p]);
        make_addtag(rs(p), addtag[p]);
        addtag[p] = 0;
    }
    if (opt4tag[p]) {
        make_opt4tag(ls(p), pl, mid, opt4tag[p]);
        make_opt4tag(rs(p), mid + 1, pr, opt4tag[p]);
        opt4tag[p] = 0;
    }
}

void min_update(ll p, ll pl, ll pr) {
    if (mintree[p] >= r) {
        make_modifytag(p, r);
        return;
    }
    if (maxtree[p] <= r || pl == pr)
        return;
    pushdown(p, pl, pr);
    ll mid = (pl + pr) / 2;
    min_update(ls(p), pl, mid);
    min_update(rs(p), mid + 1, pr);
    pushup(p);
}

void max_update(ll p, ll pl, ll pr) {
    if (maxtree[p] <= l) {
        make_modifytag(p, l);
        return;
    }
    if (mintree[p] >= l || pl == pr)
        return;
    pushdown(p, pl, pr);
    ll mid = (pl + pr) / 2;
    max_update(ls(p), pl, mid);
    max_update(rs(p), mid + 1, pr);
    pushup(p);
}

void get_ans(ll p, ll pl, ll pr) {
    if (pl == pr) {
        ans[a[pl].idx] = maxtree[p];
        return;
    }
    pushdown(p, pl, pr);
    ll mid = (pl + pr) / 2;
    get_ans(ls(p), pl, mid);
    get_ans(rs(p), mid + 1, pr);
}

int main() {
    freopen("std.in", "r", stdin);
    freopen("std.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> l >> r;
    for (ll i = 1; i <= n; i++) {
        cin >> ch >> x[i];
        if (ch == '+')
            opt[i] = 1;
        else if (ch == '-')
            opt[i] = 2;
        else if (ch == '*')
            opt[i] = 3;
        else
            opt[i] = 4;
    }
    cin >> q;
    for (ll i = 1; i <= q; i++)
        cin >> a[i].val, a[i].idx = i;
    sort(a + 1, a + q + 1);
    build(1, 1, q);
    for (ll i = 1; i <= n; i++) {
        if (opt[i] == 1)
            make_addtag(1, x[i]);
        else if (opt[i] == 2)
            make_addtag(1, -x[i]);
        else if (opt[i] == 3)
            make_multag(1, x[i]);
        else
            make_opt4tag(1, 1, q, x[i]);
        min_update(1, 1, q);
        max_update(1, 1, q);
    }
    get_ans(1, 1, q);
    for (int i = 1; i <= q; i++)
        cout << ans[i] << endl;
    return 0;
}