結果
問題 |
No.3239 Omnibus
|
ユーザー |
|
提出日時 | 2025-08-15 22:13:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 443 ms / 10,000 ms |
コード長 | 4,952 bytes |
コンパイル時間 | 1,775 ms |
コンパイル使用メモリ | 202,472 KB |
実行使用メモリ | 30,464 KB |
最終ジャッジ日時 | 2025-08-15 22:13:33 |
合計ジャッジ時間 | 13,519 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; using SS = pair<long long,long long>; using Typepos = int; class DynamicSegmentTree{ //動的再帰セグ木 二分探索はない. private: SS op(SS a,SS b){return {a.first+b.first,a.second+b.second};} static inline const SS e = {0,0}; //CEなったらv(e)を直接変える. struct Node{ Typepos pos; //葉posの頂点. SS v,all; //v->posの値,all->部分木全部. Node *LR[2]; //二分木. Node(Typepos p,SS vv):pos(p),v(vv),all(vv),LR{nullptr,nullptr}{} }; Node *root; public: Typepos siz = 1<<18; DynamicSegmentTree(){root = nullptr;} void make(Typepos N){siz = 1; while(siz < N) siz *= 2;} void setsiz(Typepos N){assert(N==(N&-N)); siz = N;} private: SS getval(Node *p){return p?p->all:e;} //ノードpのallを返す. nullptrの場合分け省く用. //葉でない[a,b)の頂点にも[a,b)の1つを割り振ることにより空間をO(N)にする 適宜割り振る所は更新. Node* update(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-op(p,v); 更新する. if(p == nullptr) return new Node(pos,v); if(p->pos == pos){ p->v = op(p->v,v); p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } Typepos m = (a+b)/2; if(pos < m){ if(pos > p->pos) swap(pos,p->pos),swap(v,p->v);//左の子のposは親のposより小さくする. p->LR[0] = update(a,m,pos,p->LR[0],v); } else{ if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく. p->LR[1] = update(m,b,pos,p->LR[1],v); } p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } Node* set(Typepos a,Typepos b,Typepos pos,Node *p,SS &v){ //p<-v 設定する. if(p == nullptr) return new Node(pos,v); if(p->pos == pos){ p->v = v; p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } Typepos m = (a+b)/2; if(pos < m){ if(pos > p->pos) swap(pos,p->pos),swap(v,p->v); //左の子のposは親のposより小さくする. p->LR[0] = set(a,m,pos,p->LR[0],v); } else{ if(pos < p->pos) swap(pos,p->pos),swap(v,p->v); //右の子は親より大きく. p->LR[1] = set(m,b,pos,p->LR[1],v); } p->all = op(getval(p->LR[0]),op(p->v,getval(p->LR[1]))); return p; } public: void update(Typepos pos,SS x){ assert(0 <= pos && pos < siz); root = update(0,siz,pos,root,x); } void set(Typepos pos,SS x){ assert(0 <= pos && pos < siz); root = set(0,siz,pos,root,x); } private: SS findans(Typepos L,Typepos R,Typepos a,Typepos b,Node *p){ if(p == nullptr || R <= a || b <= L) return e; if(L <= a && b <= R) return p->all; Typepos m = (a+b)/2; SS ret = findans(L,R,a,m,p->LR[0]); if(L <= p->pos && p->pos < R) ret = op(ret,p->v); return op(ret,findans(L,R,m,b,p->LR[1])); } public: SS rangeans(Typepos L,Typepos R){ assert(0 <= L && L <= siz && 0 <= R && R <= siz); // L>Rは許容する. if(L >= R) return e; return findans(L,R,0,siz,root); } SS allrange(){return getval(root);} SS get(Typepos pos){return rangeans(pos,pos+1);} //O(logsiz). }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n = 26*26*26; vector<DynamicSegmentTree> Z(n); int N,Q; cin >> N >> Q; string s; cin >> s; for(int i=0; i<N-2; i++){ int c1 = s.at(i)-'a',c2 = s.at(i+1)-'a',c3 = s.at(i+2)-'a'; Z.at(c1*26*26+c2*26+c3).update(i,{1,i+1}); } auto updateS = [&](int pos,char c) -> void { for(int i=pos-2; i<=pos; i++){ if(i < 0) continue; if(i+2 >= N) break; int c1 = s.at(i)-'a',c2 = s.at(i+1)-'a',c3 = s.at(i+2)-'a'; Z.at(c1*26*26+c2*26+c3).update(i,{-1,-(i+1)}); } s.at(pos) = c; for(int i=pos-2; i<=pos; i++){ if(i < 0) continue; if(i+2 >= N) break; int c1 = s.at(i)-'a',c2 = s.at(i+1)-'a',c3 = s.at(i+2)-'a'; Z.at(c1*26*26+c2*26+c3).update(i,{1,(i+1)}); } }; while(Q--){ int t; cin >> t; if(t == 1){ int pos; char c; cin >> pos >> c; pos--; updateS(pos,c); } else{ int l,r; cin >> l >> r; l--; string a; cin >> a; int pos = 0; for(auto c : a) pos *= 26,pos += c-'a'; r -= 2; if(l >= r) cout << "0\n"; else{ auto [c,s] = Z.at(pos).rangeans(l,r); s -= l*c; cout << s << "\n"; } } } }