結果

問題 No.3208 Parse AND OR Affection
コンテスト
ユーザー GOTKAKO
提出日時 2025-07-18 23:13:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 281 ms / 5,000 ms
コード長 3,737 bytes
コンパイル時間 2,379 ms
コンパイル使用メモリ 210,904 KB
実行使用メモリ 20,024 KB
最終ジャッジ日時 2025-07-18 23:13:38
合計ジャッジ時間 6,594 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

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

    int N,Q; cin >> N >> Q;
    string s; cin >> s;
    s.insert(s.begin(),'+'),N++;

    int siz = 1;
    while(siz < N) siz <<= 1;
    vector<pair<int,int>> LR(siz*2,{-1,-1});
    for(int i=siz; i<siz+N; i++) LR.at(i) = {i-siz,i-siz+1};
    
    vector<tuple<long long,long long,long long,long long,long long,int>> dat(siz);
    auto Change = [&](int l,int r) -> int {
        l += siz,r += siz;
        vector<int> Ls,Rs;
        while(l < r){
            if(l&1) Ls.push_back(l++);
            if(r&1) Rs.push_back(--r);
            l >>= 1,r >>= 1;
        }
        int ret = 2;
        for(auto pos : Ls){
            int kind = get<5>(dat.at(pos));
            if(kind < 2) ret = kind;
            else if(kind == 3) ret ^= 1;
        }
        for(int i=Rs.size(); i--;){
            int kind = get<5>(dat.at(Rs.at(i)));
            if(kind < 2) ret = kind;
            else if(kind == 3) ret ^= 1;
        }
        return ret;
    };

    for(int i=siz-1; i>0; i--){
        int l = LR.at(i*2).first,r = LR.at(i*2+1).second;
        LR.at(i) = {l,r};
        if(l == -1 || r == -1) continue;
        if(r-l == 2){
            string t = s.substr(l,2);
            if(t == "+T") dat.at(i) = {1,1,1,0,1,1};
            else if(t == "+F" || t == "^F") dat.at(i) = {0,0,1,1,0,2};
            else if(t == "*T") dat.at(i) = {1,0,1,0,1,2};
            else if(t == "*F") dat.at(i) = {0,0,0,1,0,0};
            else if(t == "^T") dat.at(i) = {1,1,0,0,1,3};
            else assert(false);
        }
        else{
            auto &[sum,s0,s1,a0,a1,change] = dat.at(i);
            int cl = get<5>(dat.at(i*2)),cr = get<5>(dat.at(i*2+1));
            {
                change = 2;
                if(cl < 2) change = cl;
                else if(cl == 3) change ^= 1;
                if(cr < 2) change = cr;
                else if(cr == 3) change ^= 1; 
            }
            bool f0 = false,f1 = true;
            for(int i=l; i<r; i+=2){
                string t = "";
                t += s.at(i),t += s.at(i+1);
                if(t == "+T"){
                    sum += a0+a1+1,a1 += a0+1,a0 = 0;
                    f0 = true,f1 = true;
                }   
                else if(t == "+F" || t == "^F") sum += a1,a0++;
                else if(t == "*T") sum += a1+1,a1++;
                else if(t == "*F") a0 += a1+1,a1 = 0,f0 = false,f1 = false;
                else if(t == "^T"){
                    sum += a0+1,swap(a0,a1),a1++;
                    f0 ^= 1,f1 ^= 1;
                }
                else assert(false);
                if(f0) s0++;
                if(f1) s1++; 
            }
        }
    }

    using SS = tuple<long long,long long,long long>;
    auto op = [&](SS &x,int pos) -> void {
        auto &[sum,zero,one] = x;
        auto [s,s0,s1,a0,a1,change] = dat.at(pos);
        sum += s+s0*zero+s1*one;
        if(change == 0) zero += one,one = 0;
        else if(change == 1) one += zero,zero = 0;
        else if(change == 3) swap(one,zero); 
        zero += a0,one += a1;
    };

    while(Q--){
        int l,r; cin >> l >> r; r++;
        
        long long answer = 0,F = 0,T = 0;
        if(s.at(l) == 'F') F++;
        else if(s.at(l) == 'T') answer++,T++;
        l++;
        if(s.at(r-1) != 'F' && s.at(r-1) != 'T') r--;
        SS v = {answer,F,T};
        l += siz,r += siz;
        assert(l%2 == 0 && r%2 == 0);
        vector<int> Rs;
        while(l < r){
            if(l&1) op(v,l),l++;
            if(r&1) Rs.push_back(--r);
            l >>= 1,r >>= 1;
        }
        for(int i=Rs.size(); i--;) op(v,Rs.at(i));
        cout << get<0>(v) << endl;
    }
}
0