#1154674 (C++17) No.876 Range Compress Query

• 問題: No.876 Range Compress Query
• ユーザー: harurun
• 提出日時: 2026-04-01 03:26:19
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 169 ms / 2,000 ms
• コード長: 4,605 bytes
• コンパイル時間: 8,844 ms
• コンパイル使用メモリ: 580,532 KB
• 実行使用メモリ: 9,088 KB
• 最終ジャッジ日時: 2026-04-03 10:51:24
• 合計ジャッジ時間: 6,641 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 18

ソースコード

#ifndef ONLINE_JUDGE
#include "header.hpp"
#else
#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/multiprecision/cpp_int.hpp>
using cpp_int=boost::multiprecision::cpp_int;
#include <boost/multiprecision/cpp_dec_float.hpp>
template<unsigned size>using cpp_float=boost::multiprecision::number<boost::multiprecision::cpp_dec_float<size>>;
template<unsigned size>using cpp_double=boost::multiprecision::number<boost::multiprecision::cpp_dec_float<size,long long>>;
#endif

using namespace std;
using ll=long long;
inline void yn(bool x){if(x){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
#define double_out(x) fixed << setprecision(x)
template<class T> inline void erase_duplicate(vector<T>& A){sort(A.begin(),A.end());A.erase(unique(A.begin(),A.end()),A.end());}
inline ll powll(ll x,ll n){ll r=1;while(n>0){if(n&1){r*=x;};x*=x;n>>=1;};return r;}


// https://hackmd.io/@tatyam-prime/DualSegmentTree
using ll = long long;
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }


template<class T>
struct DualSegmentTree{
    virtual void c(T&, const T&) = 0;
    ll size = 1, rank = 0;
    vector<T> lazy;
    const T def_lazy;
    DualSegmentTree(ll n, const T& def_value, const T& def_lazy): def_lazy(def_lazy){
        while(size < n){
            size *= 2;
            rank++;
        }
        lazy.assign(size * 2, def_lazy);
        for(ll i = size; i < size * 2; i++) lazy[i] = def_value;
    }
    DualSegmentTree(const vector<T>& v, const T& def_lazy): def_lazy(def_lazy){
        while(size < v.size()){
            size *= 2;
            rank++;
        }
        lazy.assign(size * 2, def_lazy);
        for(ll i = 0; i < v.size(); i++) lazy[size + i] = v[i];
    }
    void push(ll at){
        if(!at) return;
        ll r = 31 - __builtin_clz(at);
        for(ll i = r; i > 0; i--){
            ll a = at >> i;
            if(lazy[a] != def_lazy){
                c(lazy[a * 2], lazy[a]);
                c(lazy[a * 2 + 1], lazy[a]);
                lazy[a] = def_lazy;
            }
        }
    }
    T operator[](ll at){
        at += size;
        push(at);
        return lazy[at];
    }
    void set(ll at, const T& val){
        at += size;
        push(at);
        lazy[at] = val;
    }
    void query(ll l, ll r, const T& val){
        if(l >= r) return;
        l += size;
        r += size;
        push(l >> __builtin_ctz(l));
        push((r >> __builtin_ctz(r)) - 1);
        for(; l < r; l /= 2, r /= 2){
            if(l & 1) c(lazy[l++], val);
            if(r & 1) c(lazy[--r], val);
        }
    }
};
template<class T>
struct RAQ : DualSegmentTree<T>{
    using Base = DualSegmentTree<T>;
    void c(T& a, const T& b){ a += b; }
    RAQ(ll n, const T& def_value = T(), const T& def_lazy = T()) : Base(n, def_value, def_lazy){}
    RAQ(const vector<T>& v, const T& def_lazy = T()) : Base(v, def_lazy){}
};
template<class T>
struct RUQ : DualSegmentTree<T>{
    using Base = DualSegmentTree<T>;
    void c(T& a, const T& b){ a = b; }
    RUQ(ll n, const T& def_value, const T& def_lazy = numeric_limits<T>::max()) : Base(n, def_value, def_lazy){}
    RUQ(const vector<T>& v, const T& def_lazy = numeric_limits<T>::max()) : Base(v, def_lazy){}
};
template<class T>
struct RchmQ : DualSegmentTree<T>{
    using Base = DualSegmentTree<T>;
    void c(T& a, const T& b){ chmin(a, b); }
    RchmQ(ll n, const T& def_value, const T& def_lazy = numeric_limits<T>::max()) : Base(n, def_value, def_lazy){}
    RchmQ(const vector<T>& v, const T& def_lazy = numeric_limits<T>::max()) : Base(v, def_lazy){}
};



ll op(ll a,ll b){
    return a+b;
}

ll e(){
    return 0LL;
}

int main(){
    ll N,Q;
    cin>>N>>Q;
    vector<ll> A(N);
    for(ll i=0;i<N;i++){
        cin>>A[i];
    }
    RAQ<ll> seg1(A);
    atcoder::segtree<ll,op,e> seg2(N-1);
    for(ll i=0;i<N-1;i++){
        if(A[i]!=A[i+1]){
            seg2.set(i,1);
        }
    }
    for(ll i=0;i<Q;i++){
        ll t;
        cin>>t;
        if(t==1){
            ll l,r,x;
            cin>>l>>r>>x;
            l--;
            seg1.query(l,r,x);
            if(l-1>=0){
                if(seg1[l]==seg1[l-1]){
                    seg2.set(l-1,0);
                }else{
                    seg2.set(l-1,1);
                }
            }
            if(r<N){
                if(seg1[r-1]==seg1[r]){
                    seg2.set(r-1,0);
                }else{
                    seg2.set(r-1,1);
                }
            }
        }else{
            ll l,r;
            cin>>l>>r;
            l--;
            cout<<seg2.prod(l,r-1)+1<<endl;
        }
    }
}