結果

問題 No.2762 Counting and Deleting
コンテスト
ユーザー t9unkubj
提出日時 2025-01-13 23:06:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 198 ms / 4,000 ms
コード長 10,095 bytes
コンパイル時間 8,623 ms
コンパイル使用メモリ 316,912 KB
実行使用メモリ 14,692 KB
最終ジャッジ日時 2025-01-13 23:07:03
合計ジャッジ時間 9,188 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;

template <class T,T (*op)(T, T),class F,T (*mapping)(T,F),F (*merge)(F, F)>
struct lazy_segtree{
    int n;
    vector<T>data;
    vector<F>lazy;
    int log;
    T e;
    F id;
    lazy_segtree(int n1,T e,F id):n(n1),e(e),id(id){
        int n_=1;
        log=0;
        while(n_<=n)n_*=2,log++;
        data=vector<T>(n_*2,e);
        lazy=vector<F>(n_,id);
        n=n_;
        for(int i=n_-1;i>0;i--)update(i);
    }
    void update(int k){
        data[k]=op(data[k*2],data[k*2+1]);
    }
    void apply(int k,F x){//
        data[k]=mapping(data[k],x);
        if(k<n){
            lazy[k]=merge(lazy[k],x);
            if(lazy[k]==id)return;
            //segment tree beats! if(data[k].fail)push(k),update(k);
        }
    }
    void push(int k){//上から遅延素を伝播させる
        apply(k*2,lazy[k]);
        apply(k*2+1,lazy[k]);
        lazy[k]=id;
    }
    void set(int p,T x){
        p+=n;
        for(int i=log;i>=1;i--){
            push(p>>i);
        }
        data[p]=x;
        for(int i=1;i<=log;i++){
            update(p>>i);
        }
    }
    void apply(int l,int r,F x){
        if(l==r)return;
        l+=n,r+=n;
        for(int i=log;i>=1;i--){
            if(((l>>i)<<i)!=l)push(l>>i);
            if(((r>>i)<<i)!=r)push((r-1)>>i);
        } 
        int l2{l},r2{r};
        while(l<r){
            if(l&1)apply(l++,x);
            if(r&1)apply(--r,x);
            l>>=1,r>>=1;
        }
        l=l2,r=r2;
        for(int i=1;i<=log;i++){
            if(((l>>i)<<i)!=l)update(l>>i);
            if(((r>>i)<<i)!=r)update((r-1)>>i);
        }
    }
    T prod(int l,int r){
        l+=n,r+=n;
        for(int i=log;i>=1;i--){
            if(((l>>i)<<i)!=l)push(l>>i);
            if(((r>>i)<<i)!=r)push((r-1)>>i);
        } 
        T sml=e,smr=e;
        while(l<r){
            if(l&1)sml=op(sml,data[l++]);
            if(r&1)smr=op(data[--r],smr);
            l>>=1,r>>=1;
        }
        return op(sml,smr);
    }
    T get(int p){
        p+=n;
        for(int i=log;i>=1;i--)push(p>>i);
        return data[p];
    }
};
template<class T,class G,class F>
F modpow(T x,G p,F m){
    T ret=1%m;
    x%=m;
    while(p){
        if(p&1)ret=(1ll*ret*x)%m;
        x=(1ll*x*x)%m;
        p>>=1;
    }
    return ret;
}
template<class T>
T extgcd(T a,T b,T&x,T&y){//ax+by=gcd(a,b)となるようなもの
    if(b==0){
        x=1;
        y=0;
        return a;
    }else{
        T res=extgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return res;
    }
}
template<class T>
pair<T,T> inv(T x,T m){
    T a1,a2;
    T res=extgcd(x,m,a1,a2);
    return {a1,m/res};
}
constexpr int mod=998244353;
struct mint{
    long long val;
    inline long long fast(long long x){
        if(x<mod&&x>=0)return x;
        x%=mod;
        if(x<0)x+=mod;
        return x;
    }
    mint():val(0){}
    mint(long long val):val(fast(val)){}
    mint power(long long m)const {
        mint res(1);
        mint ret(*this);
        while(m){
           if(m&1)res*=ret;
           ret*=ret;
           m>>=1;
        }
        return res;
    }
    mint& operator++() {
        val++;
        if (val == mod) val = 0;
        return *this;
    }
    mint& operator--() {
        if (val == 0)val=mod;
        val--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }
    mint operator-() const { 
      return mint(-val);
    }
    friend mint operator +(const mint&a,const mint&b) noexcept{
        return mint(a)+=b;
    }
    friend mint operator -(const mint&a,const mint&b) noexcept{
        return mint(a)-=b;
    }
    friend mint operator *(const mint&a,const mint&b) noexcept{
        return mint(a)*=b;
    }
    friend mint operator /(const mint&a,const mint&b) noexcept{
        return mint(a)/=b;
    }
    mint& operator+=(const mint&a)noexcept{
        val+=a.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    mint& operator-=(const mint&a)noexcept{
        val-=a.val;
        if(val<0)val+=mod;
        return *this;
    }
    mint& operator*=(const mint&a){
        val*=a.val;
        val=fast(val);
        return *this;
    }
    mint& operator/=(const mint&a){
        val*=inv<long long>(a.val,mod).first;
        val=fast(val);
        return *this;
    }
    bool operator == (const mint&x)const noexcept{
        return this->val==x.val;
    }
    bool operator != (const mint&x)const noexcept{
        return this->val!=x.val;
    }
    friend ostream& operator << (ostream &os, const mint &x) noexcept {
        return os << x.val;
    }
    friend istream& operator >> (istream &is,  mint &x) noexcept {
        long long v;
        is >> v;
        x=mint(v);
        return is;
    }
};
vector<mint>fact(1,1),invfact(1,1);
void build(int n){
    if(n<(int)fact.size())return;
    fact=invfact=vector<mint>(n+1);
    fact[0]=1;
    for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i;
    invfact[n]=(1/fact[n]);
    for(int i=n-1;i>=0;i--)invfact[i]=invfact[i+1]*(i+1);
}
mint C(int a,int b){//aCb
    if(a<0||b<0||a-b<0)return mint(0);
    while((int)fact.size()<=a){
        fact.push_back(fact.back()*(fact.size()));
    }
    while((int)invfact.size()<=a){
        invfact.push_back(invfact.back()/invfact.size());
    }
    return fact[a]*invfact[b]*invfact[a-b];
}
mint P(int a,int b){
    if(a<b||b<0)return 0;
    return fact[a]*invfact[a-b];
}
//a個のものからb個を重複を許して選ぶ
mint H(int a,int b){
    return C(a+b-1,b);
}
void print(mint a) { cout << a; }
template<class T>
pair<T,T> mod_solve(T a,T b,T m){//ax=b mod mとなるxを返す
    a%=m,b%=m;if(a<0)a+=m;if(b<0)b+=m;
    T g=gcd(gcd(a,b),m);
    a/=g,b/=g,m/=g;
    if(gcd(a,m)>1)return {-1,-1};
    return {(inv(a,m).first*b)%m,inv(a,m).second};
}
template<class monoid>
struct segtree{
    int n;
    vector<monoid>node;
    static monoid e(){
        return monoid::e();
    }
    static monoid op(monoid a,monoid b){
        return monoid::op(a,b);
    }

    segtree(){}
    segtree(int n):n(n),node(n*2,e()){
        assert(0<=n);
    }
    void set(int i,monoid x){
        assert(0<=i&&i<n);
        node[i+=n]=x;
        while(i>>=1)node[i]=op(node[i<<1],node[i<<1|1]);
    }
    monoid prod(int l,int r) const {
        assert(0<=l&&l<=r&&r<=n);
        l+=n,r+=n;
        monoid sml=e(),smr=e();
        while(l<r){
            if(l&1)sml=op(sml,node[l++]);
            if(r&1)smr=op(node[--r],smr);
            l>>=1,r>>=1;
        }
        return op(sml,smr);
    }
    monoid get(int i){
        assert(0<=i&&i<=n);
		return node[i+n];
	}
    //return max val s.t. f([L,val))) = true
    template<class F>
    int max_right(int L,const F&f) const {
        assert(f(e()));
        int l=n+L;   
        int w=1;
        monoid ansL=e();
        for(;L+w<=n;l>>=1,w<<=1){
            if(l&1){
                if(!(f(op(ansL,node[l]))))break;
                ansL=op(ansL,node[l++]);
                L+=w;
            }
        }
        while(l<<=1,w>>=1){
            if(L+w<=n&&f(op(ansL,node[l]))){
                ansL=op(ansL,node[l++]);
                L+=w;
            }
        }
        return L;
    }
    //return min val s.t. f([val,R)) = true
    template<class F>
    int min_left(int R,const F&f) const {
        assert(f(e()));
        int r=n+R;   
        int w=1;
        monoid ansR=e();
        for(;R-w>=n;r>>=1,w<<=1){
            if(r&1){
                if(!(f(op(ansR,node[r-1]))))break;
                ansR=op(ansR,node[--r]);
                R-=w;
            }
        }
        while(r<<=1,w>>=1){
            if(R-w>=n&&f(op(ansR,node[r-1]))){
                ansR=op(ansR,node[--r]);
                R-=w;
            }
        }
        return R;
    }
};


struct mat{
    array<array<mint,3>,3>a;
    static mat op(mat &a, mat &b) {
        mat res{};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    (res.a[i][j] += a.a[i][k] * b.a[k][j]);
                }
            }
        }
        return res;
    }
    static mat e(){
        mat res;
        rep(i,3)res.a[i][i]=1;
        return res;
    }
};
mat zero(){
    mat res=mat::e();
    res.a[0][1]=1;
    return res;
}
mat one(){
    mat res=mat::e();
    res.a[1][0]=1;
    res.a[1][2]=1;
    return res;
}
void solve(){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    segtree<mat>seg(n);
    rep(i,n){
        seg.set(n-i-1,(s[i]=='1'?one():zero()));
    }
    set<int>st;
    rep(i,n)st.insert(i);
    while(q--){
        int t,l,r;
        cin>>t>>l>>r;
        --l,--r;
        if(t==1){
            while(1){
                auto it=st.lower_bound(l);
                if(it==st.end()||*it>r)break;
                seg.set(n-*it-1,mat::e());
                st.erase(it);
            }
        }else{
            auto R=seg.prod(n-r-1,n-l);
            cout<<R.a[0][2]+R.a[1][2]<<"\n";   
        }
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    pass_time=clock();
    int t=1;
    //cin>>t;
    while(t--)solve();
    pass_time=clock()-pass_time;
    dbg(pass_time/CLOCKS_PER_SEC);
}
0