ある区間のブロック数は、区間内で隣り合う色が異なる場所の数 \(+1\) です。

そのため、\(2\) つの区間を順に連結してできる区間のブロック数は各区間のブロック数と左側の区間の右端の色、右側の区間の左端の色から求められます。

具体的には、左の区間の右端の色を \(r\) 、右の区間の左端の色を \(l\)、区間のブロック数をそれぞれ \(cnt_l,cnt_r\) とすると、 新たに連結してできた区間のブロック数は \(l=r\) のときは \(cnt_l+cnt_r-1\) となり、それ以外のときは \(cnt_l+cnt_r\) となります。

この形でセグメント木で区間の左端の色、右端の色、ブロック数の情報を持たせて、区間クエリに答えられることがわかります。

また、区間更新についてもある区間をすべて一色に変更すると左端、右端の色が更新された色に、ブロック数が \(1\) となります。よって、遅延セグメント木でも同じように情報を持って、区間更新を行いながら区間クエリに答えられます。

時間計算量は \(\mathrm{O}((N+Q)\log N)\) となります。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;
struct S {
    int l, r;
    int cnt;
    S() : l(-1), r(-1), cnt(0) {}
    S(int x) : l(x), r(x), cnt(1) {}
};
S op(S a, S b) {
    S res;
    res.l = a.l;
    res.r = b.r;
    res.cnt = a.cnt + b.cnt - (a.r == b.l);
    return res;
}
S e() { return S(); }
S mapping(int f, S x) {
    if (f == -1) return x;
    x.l = f, x.r = f;
    x.cnt = 1;
    return x;
}
int composition(int f, int g) {
    if (f == -1) return g;
    return f;
}
int id() { return -1; }
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> c(n);
    for (auto& e : c) cin >> e;
    vector<S> v(n);
    for (int i = 0; i < n; ++i) v[i] = S(c[i]);
    atcoder::lazy_segtree<S, op, e, int, mapping, composition, id> seg(v);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            l--;
            seg.apply(l, r, x);
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            cout << seg.prod(l, r).cnt  << endl;
        }
    }
}