結果

問題 No.876 Range Compress Query
ユーザー niuezniuez
提出日時 2019-09-06 22:22:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 375 ms / 2,000 ms
コード長 3,788 bytes
コンパイル時間 1,799 ms
コンパイル使用メモリ 178,176 KB
実行使用メモリ 13,484 KB
最終ジャッジ日時 2023-09-07 00:59:25
合計ジャッジ時間 5,840 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 3 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 373 ms
12,868 KB
testcase_12 AC 302 ms
12,644 KB
testcase_13 AC 302 ms
12,852 KB
testcase_14 AC 356 ms
12,820 KB
testcase_15 AC 243 ms
13,300 KB
testcase_16 AC 352 ms
13,344 KB
testcase_17 AC 347 ms
13,484 KB
testcase_18 AC 375 ms
13,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const


struct Mono {
  i64 sum;
  i64 left;
  i64 right;
};

template<typename... Types>
struct dynarr: std::vector<Types...> {
  using std::vector<Types...>::vector;
  using size_type = typename std::vector<Types...>::size_type;
  auto&& operator[](size_type i) { return this->at(i); }
  auto&& operator[](size_type i) const { return this->at(i); }
};

template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree
{
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(Monoid, OperatorMonoid) >;
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;
  using P = function< OperatorMonoid(OperatorMonoid, int) >;

  int sz;
  vector< Monoid > data;
  vector< OperatorMonoid > lazy;
  const F f;
  const G g;
  const H h;
  const P p;
  const Monoid M1;
  const OperatorMonoid OM0;


  LazySegmentTree(int n, const F f, const G g, const H h, const P p,
                  const Monoid &M1, const OperatorMonoid OM0)
      : f(f), g(g), h(h), p(p), M1(M1), OM0(OM0)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    data.assign(2 * sz, M1);
    lazy.assign(2 * sz, OM0);
  }

  void set(int k, const Monoid &x)
  {
    data[k + sz] = x;
  }

  void build()
  {
    for(int k = sz - 1; k > 0; k--) {
      data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }
  }

  void propagate(int k, int len)
  {
    if(lazy[k] != OM0) {
      if(k < sz) {
        lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
        lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      }
      data[k] = g(data[k], p(lazy[k], len));
      lazy[k] = OM0;
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r)
  {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return data[k];
    } else if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      propagate(k, r - l);
      return data[k];
    } else {
      return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                         update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x)
  {
    return update(a, b, x, 1, 0, sz);
  }


  Monoid query(int a, int b, int k, int l, int r)
  {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return M1;
    } else if(a <= l && r <= b) {
      return data[k];
    } else {
      return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
               query(a, b, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid query(int a, int b)
  {
    return query(a, b, 1, 0, sz);
  }

  Monoid operator[](const int &k)
  {
    return query(k, k + 1);
  }
};

int main() {
  i64 n, q;
  cin >> n >> q;
  vector<Mono> a(n);
  rep(i,0,n) {
    i64 A;
    cin >> A;
    a[i] = { 0, A, A };
  }
  auto f = [](Mono a, Mono b) -> Mono {
    i64 sum = a.sum + b.sum;
    if(a.right != b.left && a.right != (i64)(-1e18) && b.left != (i64)(-1e18)) sum++;
    return { sum, a.left, b.right };
  };
  auto g = [](Mono t, i64 l) -> Mono {
    return { t.sum, 
      (t.left == (i64)-1e18 ? (i64)-1e18 : t.left + l),
      (t.right == (i64)-1e18 ? (i64)-1e18 : t.right + l) };
  };
  auto h = [](i64 x, i64 y) { return x + y; };
  auto p = [](i64 a, i64 b) { return a; };
  LazySegmentTree<Mono, i64> seg(n, f, g, h, p, { 0ll, (i64)(-1e18), (i64)(-1e18) }, 0);
  rep(i,0,n) {
    seg.set(i, a[i]);
  }
  seg.build();

  rep(Q, 0, q) {
    i64 com;
    cin >> com;
    if(com == 1) {
      i64 l, r, x;
      cin >> l >> r >> x;
      l--;
      seg.update(l, r, x);
    }
    else {
      i64 l, r;
      cin >> l >> r;
      l--;
      cout << seg.query(l, r).sum + 1 << endl;
    }
  }
}
0