結果

問題 No.3239 Omnibus
コンテスト
ユーザー GOTKAKO
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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";
            }
        }
    }
}
0