結果

問題 No.876 Range Compress Query
コンテスト
ユーザー m_tsubasa
提出日時 2019-09-30 00:25:19
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 317 ms / 2,000 ms
コード長 2,846 bytes
記録
コンパイル時間 1,531 ms
コンパイル使用メモリ 178,876 KB
実行使用メモリ 11,408 KB
最終ジャッジ日時 2024-10-03 04:45:12
合計ジャッジ時間 4,796 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// 1-indexed
template <class T, class E>
struct SegmentTreeLaze {
  // a,b:T c,d:E e:E(unit)
  // g(f(a,b),c) = f(g(a,c),g(b,c))
  // g(g(a,c),d) = g(a,h(c,d))
  // g(a,e) = a
  typedef function<T(T, T)> F;
  typedef function<T(T, E)> G;
  typedef function<E(E, E)> H;
  int n, height;
  F f;
  G g;
  H h;
  T tunit;
  E eunit;
  vector<T> dat;
  vector<E> laz;
  SegmentTreeLaze(){};
  SegmentTreeLaze(int newn, F f, G g, H h, T nt, E ne)
      : f(f), g(g), h(h), tunit(nt), eunit(ne) {
    init(newn);
  }
  void init(int newn) {
    n = 1, height = 0;
    while(n < newn) n <<= 1, ++height;
    dat.assign(n << 1, tunit);
    laz.assign(n << 1, eunit);
  }

  inline T reflect(int k) {
    return laz[k] == eunit ? dat[k] : g(dat[k], laz[k]);
  }

  inline void eval(int k) {
    if(laz[k] == eunit) return;
    laz[k << 1] = h(laz[k << 1], laz[k]);
    laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]);
    dat[k] = reflect(k);
    laz[k] = eunit;
  }

  inline void thrust(int k) {
    for(int i = height; i; --i) eval(k >> i);
  }

  void recalc(int k) {
    while(k >>= 1)
      dat[k] = f(reflect(k << 1), reflect((k << 1) | 1));
  }
  // [a,b)
  void update(int a, int b, E newdata) {
    thrust(a += n);
    thrust(b += n - 1);
    for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if(l & 1) laz[l] = h(laz[l], newdata), l++;
      if(r & 1) --r, laz[r] = h(laz[r], newdata);
    }
    recalc(a);
    recalc(b);
  }

  void set_val(int k, T newdata) {
    thrust(k += n);
    dat[k] = newdata;
    laz[k] = eunit;
    recalc(k);
  }

  // [a,b)
  T query(int a, int b) {
    thrust(a += n);
    thrust(b += n - 1);
    T vl = tunit, vr = tunit;
    for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if(l & 1) vl = f(vl, reflect(l++));
      if(r & 1) vr = f(reflect(--r), vr);
    }
    return f(vl, vr);
  }
};

struct data {
  long long ans, lef, righ;
  data(long long ans, long long lef, long long righ)
      : ans(ans), lef(lef), righ(righ) {}
};

long long n, q;

int main() {
  auto f = [](data l, data r) {
    if(l.lef == -1) return r;
    if(r.lef == -1) return l;
    return data(l.ans + r.ans - 1 + (l.righ != r.lef),
                l.lef, r.righ);
  };
  auto g = [](data l, long long x) {
    return data(l.ans, l.lef + x, l.righ + x);
  };
  auto h = [](long long l, long long x) { return l + x; };
  cin >> n >> q;
  SegmentTreeLaze<data, long long> seg(n, f, g, h,
                                       data(1, -1, -1), 0);
  for(int i = 0; i < n; ++i) {
    long long a;
    cin >> a;
    seg.set_val(i, data(1, a, a));
  }
  for(int i = 0; i < q; ++i) {
    long long c, l, r, x;
    cin >> c >> l >> r;
    if(c == 1) {
      cin >> x;
      seg.update(l - 1, r, x);
    }
    else
      cout << seg.query(l - 1, r).ans << endl;
  }
  return 0;
}
0