結果

問題 No.3208 Parse AND OR Affection
コンテスト
ユーザー Brandon Li
提出日時 2025-07-25 13:35:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,872 bytes
コンパイル時間 2,857 ms
コンパイル使用メモリ 219,900 KB
実行使用メモリ 12,840 KB
最終ジャッジ日時 2025-07-25 13:35:22
合計ジャッジ時間 7,352 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#define dbgn(...) 0
#endif

const int ID = 0, NOT = 1, SET_T = 2, SET_F = 3;
int n, q, m, block_size;
vector<int> v, t;
vector<int> pref_not;
vector<int> prev_stable, next_stable, next_stable_type;
vector<int> val_q_stable;
vector<vector<vector<int>>> count_v_par;
vector<vector<int>> count_pnp;

ll a_query(int q, int l) {
    if (l > q) {
        return 0;
    }
    ll ans = 0;
    int k_s = prev_stable[q];

    int p_end1 = min(q, k_s);
    if (l <= p_end1) {
        if (val_q_stable[q] == 1) {
            ans += (ll)p_end1 - l + 1;
        }
    }

    int p_start2 = max(l, k_s + 1);
    if (p_start2 <= q) {
        int par_q_minus_1 = (q > 1) ? (pref_not[q - 1] % 2) : 0;
        
        int target_par_T = par_q_minus_1;
        ans += count_v_par[1][target_par_T][q] - count_v_par[1][target_par_T][p_start2 - 1];

        int target_par_F = (par_q_minus_1 - 1 + 2) % 2;
        ans += count_v_par[0][target_par_F][q] - count_v_par[0][target_par_F][p_start2 - 1];
    }
    return ans;
}

ll count_t(int p, int l, int r) {
    if (l > r) {
        return 0;
    }
    ll ans = 0;

    if (l <= p && p <= r && v[p] == 1) {
        ans += 1;
    }

    int q_range_start = max(l, p + 1);
    if (q_range_start > r) {
        return ans;
    }

    int k_s = next_stable[p];

    int q_end1 = min(r, k_s);
    if (q_range_start <= q_end1) {
        int par_p_minus_1 = (p > 1) ? (pref_not[p - 1] % 2) : 0;
        int target_par = (1 - v[p] + par_p_minus_1) % 2;
        ans += count_pnp[target_par][q_end1] - count_pnp[target_par][q_range_start - 1];
    }
    
    int q_start2 = max(q_range_start, k_s + 1);
    if (q_start2 <= r) {
        int stable_val = next_stable_type[p];
        int par_at_k_s = (k_s > 0) ? (pref_not[k_s] % 2) : 0;
        int target_par = (1 - stable_val + par_at_k_s) % 2;
        ans += count_pnp[target_par][r] - count_pnp[target_par][q_start2 - 1];
    }

    return ans;
}

void pre(const string& x) {
    m = (n + 1) / 2;
    block_size = sqrt(m);
    if (block_size == 0) {
        block_size = 1;
    }
    
    v.resize(m + 1);
    t.resize(m + 1);
    pref_not.resize(m + 1, 0);

    for (int p = 1; p <= m; ++p) {
        v[p] = (x[2 * p - 2] == 'T');
    }

    for (int k = 1; k < m; ++k) {
        char op = x[2 * k - 1];
        int val_next = (x[2 * k] == 'T');
        if (op == '+') {
            t[k] = val_next ? SET_T : ID;
        } else if (op == '*') {
            t[k] = val_next ? ID : SET_F;
        } else {
            t[k] = val_next ? NOT : ID;
        }
    }

    for (int k = 1; k < m; ++k) {
        pref_not[k] = pref_not[k - 1] + (t[k] == NOT);
    }
    
    prev_stable.resize(m + 2, 0);
    int last_or_t = 0, last_and_f = 0;
    for (int i = 1; i <= m; ++i) {
        if (i > 1) {
            if (t[i - 1] == SET_T) last_or_t = i - 1;
            if (t[i - 1] == SET_F) last_and_f = i - 1;
        }
        prev_stable[i] = max(last_or_t, last_and_f);
    }

    next_stable.resize(m + 1, m + 1);
    next_stable_type.resize(m + 1, 0);
    int next_or_t = m + 1, next_and_f = m + 1;
    for (int p = m - 1; p >= 1; --p) {
        if (t[p] == SET_T) next_or_t = p;
        if (t[p] == SET_F) next_and_f = p;
        if (next_or_t < next_and_f) {
            next_stable[p] = next_or_t;
            next_stable_type[p] = 1;
        } else {
            next_stable[p] = next_and_f;
            next_stable_type[p] = 0;
        }
    }
    
    val_q_stable.resize(m + 1, 0);
    for (int i = 1; i <= m; ++i) {
        int k_s = prev_stable[i];
        if (k_s > 0) {
            int val_at_stable = (t[k_s] == SET_T);
            int nots_after = pref_not[i - 1] - pref_not[k_s - 1];
            val_q_stable[i] = val_at_stable ^ (nots_after % 2);
        }
    }

    count_v_par.assign(2, vector<vector<int>>(2, vector<int>(m + 1, 0)));
    for (int p = 1; p <= m; ++p) {
        for (int val = 0; val < 2; ++val) {
            for (int par = 0; par < 2; ++par) {
                count_v_par[val][par][p] = count_v_par[val][par][p - 1];
            }
        }
        int par_p_minus_1 = (p > 1) ? (pref_not[p - 1] % 2) : 0;
        count_v_par[v[p]][par_p_minus_1][p]++;
    }
    
    count_pnp.assign(2, vector<int>(m + 1, 0));
    for (int i = 1; i <= m; ++i) {
        count_pnp[0][i] = count_pnp[0][i - 1];
        count_pnp[1][i] = count_pnp[1][i - 1];
        int par_i_minus_1 = (i > 1) ? (pref_not[i - 1] % 2) : 0;
        count_pnp[par_i_minus_1][i]++;
    }
}

struct QUERY {
    int l, r, og_idx, bl;
    bool operator<(const QUERY& other) const {
        if (bl != other.bl) {
            return bl < other.bl;
        }
        return (bl % 2) ? (r < other.r) : (r > other.r);
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    string x;
    cin >> x;

    pre(x);

    vector<QUERY> queries(q);
    for (int i = 0; i < q; i++) {
        int l_in, r_in;
        cin >> l_in >> r_in;
        queries[i].l = (l_in + 1) / 2;
        queries[i].r = (r_in + 1) / 2;
        queries[i].og_idx = i;
        queries[i].bl = queries[i].l / block_size;
    }

    sort(queries.begin(), queries.end());

    vector<ll> ans(q);
    int cl = 1, cr = 0;
    ll cur_ans = 0;

    for (const auto& Q : queries) {
        while (cl > Q.l) {
            cl--;
            cur_ans += count_t(cl, cl, cr);
        }
        while (cr < Q.r) {
            cr++;
            cur_ans += a_query(cr, cl);
        }
        while (cl < Q.l) {
            cur_ans -= count_t(cl, cl, cr);
            cl++;
        }
        while (cr > Q.r) {
            cur_ans -= a_query(cr, cl);
            cr--;
        }
        ans[Q.og_idx] = cur_ans;
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}
0