Submission #67751603

---

Source Code Expand

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;




#define rep(i, N) for (int i = 0; i < N; i++)
#define repn(i, n, N) for (int i = n; i < N; i++)
#define fore(i, x) for(auto i : x)
#define rep1(i, N) for(int i = 1; i <= N; i++)
#define ll long long
#define ull unsigned long long

template<class T> inline bool chmin(T& a, T b){ if(a > b){ a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return 1;} return 0;}

const long long INF_LL = 1LL << 60;
const int INF_I = 1 << 30;

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

int RandInt(int a, int b){
    return a + (ll)rand() % (ll)(b - a + 1);
}

double RandDouble(){
    return 1.0 * rand() / RAND_MAX;
}

void overflow(ll a) {if(a < 0) throw;}

struct S{
    int l_len, r_len;
    char l, r;
    int mx_len;
    int len;
};


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


S op(S a, S b){
    S s;
    s.len = a.len + b.len;

   

    //真ん中でつながる
    if(a.r == b.l){
        s.mx_len =max({a.mx_len, b.mx_len, a.r_len + b.l_len});
    
        if(a.r_len == a.l_len && a.r_len == a.len){
            s.l_len = a.r_len + b.l_len;
            s.l = a.l;
        }
        else{
            s.l_len = a.l_len;
            s.l = a.l;
        }

        if(b.l_len == b.r_len && b.l_len == b.len){
            s.r_len = b.r_len + a.r_len;
            s.r = b.r;
        }else{
            s.r_len = b.r_len;
            s.r = b.r;
        }
    }else{
        s.mx_len = max(a.mx_len, b.mx_len);

        s.l_len = a.l_len;
        s.l = a.l;
        s.r_len = b.r_len;
        s.r = b.r;
    }

    return s;
}


int main(){
    int N, Q; cin >> N >> Q;
    string s; cin >> s;
    vector<S> v(N);
    rep(i, N){
        S a = {1, 1, s[i], s[i], 1, 1};
        v[i] = a;
    }

    atcoder::segtree<S, op, e> seg(v);

    for(;Q--;){
        int q; cin >> q;
        if(q == 1){
            int i; char x; cin >> i >> x; i--;
        
            S a = {1, 1, x, x, 1, 1};
            seg.set(i, a);
        }
        if(q == 2){
            int l, r; cin >> l >> r;
            l--;

        
            S a = seg.prod(l, r);
            cout << a.mx_len << "\n";
        }
    }
}

Submission Info

Judge Result