#1156725 (C++23) No.3208 Parse AND OR Affection

• 問題: No.3208 Parse AND OR Affection
• ユーザー: amesyu
• 提出日時: 2026-04-07 00:02:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 202 ms / 5,000 ms
• コード長: 4,970 bytes
• コンパイル時間: 1,529 ms
• コンパイル使用メモリ: 181,468 KB
• 実行使用メモリ: 18,408 KB
• 最終ジャッジ日時: 2026-04-07 00:02:16
• 合計ジャッジ時間: 6,008 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 20

ソースコード

// VS Gemini 3.1 Pro By amesyu

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// セグメント木のノードデータ
struct Data {
    long long c0;
    long long c1;
    long long sum;
};

// 遅延評価の作用素
struct Lazy {
    int m0;
    int m1;
    long long s0;
    long long s1;
};

Data op(Data a, Data b) {
    return {a.c0 + b.c0, a.c1 + b.c1, a.sum + b.sum};
}

Data e() {
    return {0, 0, 0};
}

Data mapping(Lazy f, Data x) {
    Data res;
    res.sum = x.sum + x.c0 * f.s0 + x.c1 * f.s1;
    res.c0 = (f.m0 == 0 ? x.c0 : 0) + (f.m1 == 0 ? x.c1 : 0);
    res.c1 = (f.m0 == 1 ? x.c0 : 0) + (f.m1 == 1 ? x.c1 : 0);
    return res;
}

Lazy composition(Lazy f, Lazy g) {
    Lazy res;
    res.m0 = (g.m0 == 0 ? f.m0 : f.m1);
    res.m1 = (g.m1 == 0 ? f.m0 : f.m1);
    res.s0 = g.s0 + (g.m0 == 0 ? f.s0 : f.s1);
    res.s1 = g.s1 + (g.m1 == 0 ? f.s0 : f.s1);
    return res;
}

Lazy id() {
    return {0, 1, 0, 0};
}

// 自前実装の遅延評価セグメント木
struct LazySegmentTree {
    int n, size, log;
    vector<Data> d;
    vector<Lazy> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, Lazy f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }

    LazySegmentTree(int n) : n(n) {
        log = 0;
        while ((1U << log) < (unsigned int)(n)) log++;
        size = 1 << log;
        d.assign(2 * size, e());
        lz.assign(size, id());
    }

    void set(int p, Data x) {
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    Data prod(int l, int r) {
        if (l == r) return e();
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        Data sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    void apply(int l, int r, Lazy f) {
        if (l == r) return;
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) all_apply(l++, f);
            if (r & 1) all_apply(--r, f);
            l >>= 1;
            r >>= 1;
        }
        l = l2;
        r = r2;
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
};

struct Query {
    int L, id;
};

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    string X;
    cin >> X;

    // 奇数インデックスの要素数
    int M = (N + 1) / 2;
    vector<vector<Query>> queries(M + 1);
    for (int k = 0; k < Q; ++k) {
        int L, R;
        cin >> L >> R;
        int idx_L = (L + 1) / 2;
        int idx_R = (R + 1) / 2;
        queries[idx_R].push_back({idx_L, k});
    }

    LazySegmentTree seg(M);
    vector<long long> ans(Q);

    // 現在の '1' を累積和に足し込む作用素
    Lazy f_add = {0, 1, 0, 1};

    for (int idx = 1; idx <= M; ++idx) {
        // 1. 既存の要素に関数 f を適用
        if (idx > 1) {
            char op_char = X[2 * idx - 3];
            char val_char = X[2 * idx - 2];
            int m0, m1;
            if (op_char == '+') {
                if (val_char == 'T') { m0 = 1; m1 = 1; }
                else                 { m0 = 0; m1 = 1; }
            } else if (op_char == '*') {
                if (val_char == 'T') { m0 = 0; m1 = 1; }
                else                 { m0 = 0; m1 = 0; }
            } else if (op_char == '^') {
                if (val_char == 'T') { m0 = 1; m1 = 0; }
                else                 { m0 = 0; m1 = 1; }
            }
            Lazy f = {m0, m1, 0, 0};
            seg.apply(0, idx - 1, f);
        }

        // 2. 新しい要素 j の初期化と追加
        char val_char = X[2 * idx - 2];
        Data x = {0, 0, 0};
        if (val_char == 'T') x.c1 = 1;
        else                 x.c0 = 1;
        seg.set(idx - 1, x);

        // 3. 現在の値を累積和に加算
        seg.apply(0, idx, f_add);

        // 4. クエリに答える
        for (const auto& q : queries[idx]) {
            ans[q.id] = seg.prod(q.L - 1, idx).sum;
        }
    }

    for (int k = 0; k < Q; ++k) {
        cout << ans[k] << "\n";
    }

    return 0;
}