結果

問題 No.3208 Parse AND OR Affection
コンテスト
ユーザー hitonanode
提出日時 2025-07-18 22:11:25
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 104 ms / 5,000 ms
コード長 1,922 bytes
コンパイル時間 1,273 ms
コンパイル使用メモリ 117,012 KB
実行使用メモリ 30,956 KB
最終ジャッジ日時 2025-07-18 22:11:30
合計ジャッジ時間 4,011 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <ios>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using lint = long long;

#include <atcoder/segtree>

struct S {
    lint n0 = 0;
    lint n1 = 0;
    lint v00 = 0;
    lint v01 = 0;
    lint v10 = 0;
    lint v11 = 0;
    lint v01e = 0;
    lint v11e = 0;
    lint n1e = 0;
};

S op(S l, S r) {
    S res;
    res.n0 = r.n0 + l.n0 * r.v00 + l.n1 * r.v10;
    res.n1 = r.n1 + l.n0 * r.v01 + l.n1 * r.v11;
    res.v00 = l.v00 * r.v00 + l.v01 * r.v10;
    res.v01 = l.v00 * r.v01 + l.v01 * r.v11;
    res.v10 = l.v10 * r.v00 + l.v11 * r.v10;
    res.v11 = l.v10 * r.v01 + l.v11 * r.v11;
    res.v01e = l.v01e + l.v00 * r.v01e + l.v01 * r.v11e;
    res.v11e = l.v11e + l.v10 * r.v01e + l.v11 * r.v11e;
    res.n1e = l.n1e + r.n1e + l.n0 * r.v01e + l.n1 * r.v11e;
    return res;
}

S e() { return {0, 0, 1, 0, 0, 1, 0, 0, 0}; }
S Gen(string c) {
    if (c == "F") return {1, 0, 0, 0, 0, 0, 0, 0, 0};
    if (c == "T") return {0, 1, 0, 0, 0, 0, 0, 0, 1};
    if (c == "+F") return {1, 0, 1, 0, 0, 1, 0, 1, 0};
    if (c == "+T") return {0, 1, 0, 1, 0, 1, 1, 1, 1};
    if (c == "*F") return {1, 0, 1, 0, 1, 0, 0, 0, 0};
    if (c == "*T") return {0, 1, 1, 0, 0, 1, 0, 1, 1};
    if (c == "^F") return {1, 0, 1, 0, 0, 1, 0, 1, 0};
    if (c == "^T") return {0, 1, 0, 1, 1, 0, 1, 0, 1};
    assert(false);
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, Q;
    string X;
    cin >> N >> Q >> X;
    vector<S> init;
    for (int i = 1; i < N; i += 2) init.emplace_back(Gen(X.substr(i, 2)));

    const atcoder::segtree<S, op, e> seg(init);

    while (Q--) {
        int L, R;
        cin >> L >> R;
        --L;
        if (L % 2) ++L;
        if (R % 2 == 0) --R;

        if (L >= R) {
            cout << 0 << '\n';
        } else {
            cout << op(Gen(X.substr(L, 1)), seg.prod(L / 2, R / 2)).n1e << '\n';
        }
    }
}
0