#1175096 (C++23(gnu拡張gcc16)) No.876 Range Compress Query

• 問題: No.876 Range Compress Query
• ユーザー: 👑 希丝缇娜菲贝尔
• 提出日時: 2026-08-06 02:21:43
• 言語: C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 31 ms / 2,000 ms
• コード長: 12,807 bytes
• コンパイル時間: 2,665 ms
• コンパイル使用メモリ: 365,284 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-06 02:21:49
• 合計ジャッジ時間: 4,759 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
// #include "atcoder/all"
namespace atcoder{}
using namespace atcoder;

namespace SistineFibel{
    // #define all(x) (x).begin(),(x).end()
    #define return(statement) return (statement),void();
    // bool YON(bool a,bool upp=false){if(a){std::cout<<(upp?"YES\n":"Yes\n");}else{std::cout<<(upp?"NO\n":"No\n");}return a;}
    using I = int;
    using i32 = int;
    using i64 = long long;
    using u32 = unsigned int;
    using u64 = unsigned long long;
    using Int = long long;
    using ll = long long;
    using ld = long double;
    using ull = unsigned long long;
    using uint = unsigned;
    using pii = pair<int, int>;
    using pll = pair<ll, ll>;
    using pdd = pair<ld, ld>;
    using tuplis = array<ll, 3>;
    template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
    const ll LINF=0x1fffffffffffffff;
    const ll MINF=0x7fffffffffff;
    const int INF=0x3fffffff;
    const int MOD=1000000007;
    const int MODD=998244353;
    const ld DINF=INFINITY;
    const ld PI=3.14159265358979323846;
    const ll dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
    const ll dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
    #define overload5(a,b,c,d,e,name,...) name
    #define overload4(a,b,c,d,name,...) name
    #define overload3(a,b,c,name,...) name
    #define rep1(n) rep2(_,n)
    #define rep2(i,n) rep3(i,0,n)
    #define rep3(i,a,b) for(ll i=a;i<(b);i++)
    #define rep4(i,a,b,c) for(ll i=a;i<(b);i+=(c))
    #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
    #define rrep1(n) rrep2(_,n)
    #define rrep2(i,n) for(ll i=n;i--;)
    #define rrep3(i,a,b) for(ll i=b;i-->(a);)
    #define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
    #define each1(i,a) for(auto&&i:a)
    #define each2(x,y,a) for(auto&&[x,y]:a)
    #define each3(x,y,z,a) for(auto&&[x,y,z]:a)
    #define each4(w,x,y,z,a) for(auto&&[w,x,y,z]:a)
    #define each(...) overload5(__VA_ARGS__,each4,each3,each2,each1)(__VA_ARGS__)
    #define all1(i) begin(i),end(i)
    #define all2(i,a) begin(i),begin(i)+a
    #define all3(i,a,b) begin(i)+a,begin(i)+b
    #define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
    #define rall1(i) rbegin(i),rend(i)
    #define rall2(i,a) rbegin(i),rbegin(i)+a
    #define rall3(i,a,b) rbegin(i)+a,rbegin(i)+b
    #define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
    #define sum(...) accumulate(all(__VA_ARGS__),0LL)
    #define dsum(...) accumulate(all(__VA_ARGS__),0.0L)
    #define Msum(...) accumulate(all(__VA_ARGS__),mint{})
    #define elif else if
    #define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
    #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
    #define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
    #define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
    #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
    #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
    #define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)
    #define vec(type,name,...) vector<type>name(__VA_ARGS__)
    #define arr(type,name,size) array<type,size>name
    #define VEC(type,name,size) vector<type>name(size);in(name)
    #define ARR(type,name,size) array<type,size>name;in(name)
    #define vv(type,name,h,...) vector name(h,vector<type>(__VA_ARGS__))
    #define VV(type,name,h,w) vector name(h,vector<type>(w));in(name)
    #define vvv(type,name,h,w,...) vector name(h,vector(w,vector<type>(__VA_ARGS__)))    

    template<class T> ll sz(const T& a){ return size(a); }
    template<class T, class U> ll count(const T& a, const U& b){ return count(all(a), b); }
    template<class T, class F> ll count_if(const T& a, F b){ return count_if(all(a), b); }
    template<class T, class F> void filter(T& a, F b){ a.erase(remove_if(all(a), not_fn(b)), a.end()); }
    template<class T, class F = less<>> void sor(T& a, F b = F{}){ sort(all(a), b); }
    template<class T> void rev(T& a){ reverse(all(a)); }
    template<class T> void uniq(T& a){ sor(a); a.erase(unique(all(a)), end(a)); }
    ll popcnt(ull a){ return __builtin_popcountll(a); }
    ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
    ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
    template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
    template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
    template<class T> bool chmin(T& a, const T& b){ return a > b ? a = b, 1 : 0; }
    template<class T> bool chmax(T& a, const T& b){ return a < b ? a = b, 1 : 0; }
    template<class T, class U> bool chmin(T& a, const U& b){ return a > b ? a = b, 1 : 0; }
    template<class T, class U> bool chmax(T& a, const U& b){ return a < b ? a = b, 1 : 0; }
    vector<ll> iota(ll n, ll begin = 0){ vector<ll> a(n); iota(a.begin(), a.end(), begin); return a; }
    vector<pll> factor(ull x){ vector<pll> ans; for(ull i = 2; i * i <= x; i++) if(x % i == 0){ ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; }
    vector<ll> divisor(ull x){ vector<ll> ans; for(ull i = 1; i * i <= x; i++) if(x % i == 0) ans.push_back(i); rrep(i, ans.size() - (ans.back() * ans.back() == x)) ans.push_back(x / ans[i]); return ans; }
    template<class T> unordered_map<T, ll> press(vector<T> a){ uniq(a); unordered_map<T, ll> ans; rep(i, a.size()) ans[a[i]] = i; return ans; }
    template<class T> auto run_press(const T& a){ vector<pair<decay_t<decltype(a[0])>, ll>> ans; each(x, a){ if(ans.empty() || ans.back().first != x) ans.emplace_back(x, 1); else ans.back().second++; } return ans; }
    
    template<class... Ts> void in(Ts&... t);
    [[maybe_unused]] void print(){}
    template<class T, class... Ts> void print(const T& t, const Ts&... ts);
    template<class... Ts> void out(const Ts&... ts){ print(ts...); cout << '\n'; }
    namespace IO{
        #define VOID(a) decltype(void(a))
        struct S{ S(){ cin.tie(nullptr)->sync_with_stdio(0); fixed(cout).precision(12); } }S;
        template<int I> struct P : P<I-1>{};
        template<> struct P<0>{};
        template<class T> void i(T& t){ i(t, P<3>{}); }
        void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
        template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
        template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
        template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){ in(get<idx>(t)...); }
        template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ ituple(t, make_index_sequence<tuple_size<T>::value>{}); }
        template<class T> void o(const T& t){ o(t, P<4>{}); }
        template<size_t N> void o(const char (&t)[N], P<4>){ cout << t; }
        template<class T, size_t N> void o(const T (&t)[N], P<3>){ o(t[0]); for(size_t i = 1; i < N; i++){ o(' '); o(t[i]); } }
        template<class T> auto o(const T& t, P<2>) -> VOID(cout << t){ cout << t; }
        template<class T> auto o(const T& t, P<1>) -> VOID(begin(t)){ bool first = 1; for(auto&& x : t) { if(first) first = 0; else o(' '); o(x); } }
        template<class T, size_t... idx> void otuple(const T& t, index_sequence<idx...>){ print(get<idx>(t)...); }
        template<class T> auto o(T& t, P<0>) -> VOID(tuple_size<T>{}){ otuple(t, make_index_sequence<tuple_size<T>::value>{}); }
        #undef VOID
    }
    template<class... Ts> void in(Ts&... t){ (IO::i(t), ...); }
    template<class T, class... Ts> void print(const T& t, const Ts&... ts){ IO::o(t); (IO::o((cout << ' ', ts)), ...); }
    #undef unpack
    constexpr ll debug_const(ll judge, ll debug) {
    #ifdef DEBUG
        return debug;
    #else
        return judge;
    #endif
    }
    #ifdef DEBUG
    ll __lg(ull x){ return 63 - __builtin_clzll(x); }
    #define debug(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
    #else
    #define debug(...) void(0)
    #endif
    
    template<class T>
    using v = vector<T>; 
    template<class T, std::size_t N>
    using a = array<T, N>;
    template <typename T>
    T pop(deque<T> &que) {
      T a = que.front();
      que.pop_front();
      return a;
    }
    template <class T, class Container, class Compare>
    T pop(priority_queue<T, Container, Compare> &que) {
      T a = que.top();
      que.pop();
      return a;
    }
    template <typename T>
    T pop(v<T> &que) {
      T a = que.back();
      que.pop_back();
      return a;
    }
    template <typename T>
    T pop(stack<T> &que) {
      T a = que.top();
      que.pop();
      return a;
    }
    #define YESNO(yes,no) void yes(bool i = 1){ out(i?#yes:#no); } void no(){ out(#no); }
    YESNO(first, second)
    YESNO(First, Second)
    YESNO(Yes, No)
    YESNO(YES, NO)
    YESNO(possible, impossible)
    YESNO(Possible, Impossible)
    YESNO(POSSIBLE, IMPOSSIBLE)

    template <typename F>
    ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
      if (check_ok) assert(check(ok));
      while (llabs(ok - ng) > 1) {
        auto x = (ng + ok) / 2;
        (check(x) ? ok : ng) = x;
      }
      return ok;
    }
    template <typename F>
    double binary_search_real(F check, double ok, double ng, int iter = 100) {
      rep(iter) {
        double x = (ok + ng) / 2;
        (check(x) ? ok : ng) = x;
      }
      double ans = (ok + ng) / 2;
      return ans;
    }
    template <typename T, typename U>
    v<T> cumsum(const v<U> &A, int off = 1) {
      int N = A.size();
      v<T> B(N + 1);
      rep(i, N) { B[i + 1] = B[i] + A[i]; }
      if (off == 0) B.erase(B.begin());
      return B;
    }
    #ifndef DEBUG 
      #define assert(x) (void(0))
    #endif 
} //NAMESPCACE SistineFibel
using namespace SistineFibel;
#define pb push_back
#define em emplace_back
#define fst first
#define snd second
#define is insert
#define dbg debug
#define as(...) assert(__VA_ARGS__)
#define el '\n'


template <class S, S (op)(S, S)>
struct Segtree {
  int n, s;
  S e;
 	v<S> d;
  Segtree() = default;
  Segtree(unsigned n, S e) : n(n), s(bit_ceil(n)), e(e) {
    d.assign(2 * s, e);
  }
  Segtree(const vector<S>& v, S e) : Segtree(v.size(), e) {
    ranges::copy(v, d.begin() + s);
    for (int i = s - 1; i >= 1; i--)
      d[i] = op(d[2 * i], d[2 * i + 1]);
  }
  void set(int p, S x) {
    d[p += s] = x;
    while ((p >>= 1) >= 1)
      d[p] = op(d[2 * p], d[2 * p + 1]);
  }
  S get(int p) {
    return d[p + s];
  }
  S prod(int l, int r) {
    S sml = e, smr = e;
    l += s, r += s;
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return op(sml, smr);
  }
  template <class G>
  int max_right(int l, G f) {
    if (l == n) return n;
    l += s;
    S sm = e;
    while (1) {
      while (l % 2 == 0) l >>= 1;
      S t = op(sm, d[l]);
      if (!f(t)) break;
      sm = t;
      if (l++, (l & -l) == l) return n;
    }
    while (l < s) {
      l = 2 * l;
      if (S t = op(sm, d[l]); f(t)) sm = t, l++;
    }
    return l - s;
  }
  template <class F>
  int min_left(int r, F f) {
    if (r == 0) return 0;
    r += s;
    S sm = e;
    while (1) {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      S t = op(d[r], sm);
      if (!f(t)) break;
      sm = t;
      if ((r & -r) == r) return 0;
    }
    while (r < s) {
      r = 2 * r + 1;
      if (S t = op(d[r], sm); f(t)) sm = t, r--;
    }
    return r + 1 - s;
  }
};

int op(int x, int y) {return x + y;}

auto Mainsol = [](){
  INT(N, Q);
  VEC(I, A, N);
  vec(I, B, N + 10);
  Segtree<int, op> segt(N + 10, 0);
  rep(i, N - 1) {
  	B[i] = A[i + 1] - A[i];
  	if(B[i] != 0) segt.set(i, 1);
  }

#ifdef DEBUG
print("segt : "); 
rep(i, N - 1) print(segt.get(i), "");
out();
print("B : "); out(B);
#endif 

  rep(Q) {
  	INT(o);
  	if(o == 1) {
  		INT(l, r, x); l --, r --;
  		if(l) {
  			l -= 1;
	  		B[l] += x; 
	  		if(B[l] != 0) segt.set(l, 1); else segt.set(l, 0);
  		}
  		B[r] -= x;
  		if(B[r] != 0) segt.set(r, 1); else segt.set(r, 0);
#ifdef DEBUG
print("when: ", l, r, x, '\n');
print("segt : "); 
rep(i, N - 1) print(segt.get(i), "");
out(); 
print("B : "); out(B);
#endif 
  	} elif(o == 2) {
  		INT(l, r); l --, r --;
  		ll ans = 1;
  		ans += segt.prod(l, r);
  		out(ans);
  	}
  }

};

string MAIN = []() {
  Int T__ = 1;
  // in(T__); // check it!!!!
  rep(TestCase, T__){dbg(TestCase); Mainsol();}
  return "Fibel";
}();

int32_t main(){return "Sistine", 0;}
//test
/*

*/

//============================================================================//
//==                        SISTINE_FIBEL  システィーナ=フィーベ           ==//
//============================================================================//