結果
問題 |
No.3208 Parse AND OR Affection
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; } }