Submission #67731388

---

Source Code Expand

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#include"atcoder/all"
using namespace atcoder;
typedef modint998244353 mi;
using namespace std;
#define all(a) a.begin(),a.end()
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll mod=998244353;
constexpr ll inf=3e18;

struct S{
    int max_len;
    char lchar,rchar;
    int llen,rlen;
    bool cnct;
};
S op(S lhs,S rhs){
    if(lhs.cnct&&rhs.cnct){
        if(lhs.rchar==rhs.lchar){
            return {lhs.max_len+rhs.max_len,lhs.lchar,rhs.rchar,lhs.max_len+rhs.max_len,lhs.max_len+rhs.max_len,1};
        }
        else{
            return {max(lhs.max_len,rhs.max_len),lhs.lchar,rhs.rchar,lhs.llen,rhs.rlen,0};
        }
    }
    else{
        int nmaxlen=max(lhs.max_len,rhs.max_len);
        if(lhs.rchar==rhs.lchar)nmaxlen=max(nmaxlen,lhs.rlen+rhs.llen);
        char nlchar=lhs.lchar;
        char nrchar=rhs.rchar;
        int nllen=lhs.llen;
        if(lhs.cnct&&lhs.rchar==rhs.lchar)nllen+=rhs.llen;
        int nrlen=rhs.rlen;
        if(rhs.cnct&&rhs.lchar==lhs.rchar)nrlen+=lhs.rlen;
        return {nmaxlen,nlchar,nrchar,nllen,nrlen,0};
    }

}
S e(){
    return {0,0,0,0,0,0};
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;

    vector<S>init(n);
    rep(i,n)init[i]={1,s[i],s[i],1,1,1};
    segtree<S,op,e> seg(init);

    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int i;
            char x;
            cin>>i>>x;
            i--;
            seg.set(i,{1,x,x,1,1,1});
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<seg.prod(l-1,r).max_len<<endl;
        }
    }
}

Submission Info

Judge Result