結果

問題 No.876 Range Compress Query
ユーザー niuezniuez
提出日時 2019-09-06 22:32:07
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 397 ms / 2,000 ms
コード長 3,254 bytes
コンパイル時間 2,332 ms
コンパイル使用メモリ 180,744 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-06-24 19:53:13
合計ジャッジ時間 6,520 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 4 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 389 ms
14,976 KB
testcase_12 AC 318 ms
14,592 KB
testcase_13 AC 326 ms
14,976 KB
testcase_14 AC 391 ms
14,848 KB
testcase_15 AC 265 ms
15,360 KB
testcase_16 AC 386 ms
15,872 KB
testcase_17 AC 392 ms
16,000 KB
testcase_18 AC 397 ms
15,872 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

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); }
};

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

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

struct lazy_segment_tree {
  using T = Mono;
  using L = i64;
  T t_ide() { return {0, (i64)-1e18, (i64)-1e18}; }
  L l_ide() { return 0; }
  T ope(const T& a, const T& b) {
    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 };
  }
  L lazy_ope(const L& a, const L& b) { return a + b; }
  T effect(const T& t, const L& l, const i64 len) { return { t.sum, 
    (t.left == (i64)-1e18 ? (i64)-1e18 : t.left + l),
    (t.right == (i64)-1e18 ? (i64)-1e18 : t.right + l) };
  }

  i64 n;
  vector<T> node;
  vector<L> lazy;
  vector<bool> flag;

  /* create lazy_segment_tree for sequence [t_ide; sz]A */
  lazy_segment_tree(vector<T> init) {
    n = 1;
    while(n < init.size()) n *= 2;
    node.assign(n * 2, t_ide());
    lazy.assign(n * 2, l_ide());
    flag.assign(n * 2, false);
    rep(i, 0, init.size()) node[i + n - 1] = init[i];
    for(int i = n - 2; i >= 0;i--) node[i] = ope(node[i * 2 + 1], node[i * 2 + 2]);
  }
  

  void eval(i64 l, i64 r, i64 k) {
    if(flag[k]) {
      node[k] = effect(node[k], lazy[k], r - l);
      
      if(r - l > 1) {
        lazy[k * 2 + 1] = lazy_ope(lazy[k * 2 + 1], lazy[k]);
        flag[k * 2 + 1] = true;
        lazy[k * 2 + 2] = lazy_ope(lazy[k * 2 + 2], lazy[k]);
        flag[k * 2 + 2] = true;
      }

      flag[k] = false;
      lazy[k] = l_ide();
    }
  }
  
  /* for i in [a, b) effect(a[i], lx) */
  void update(i64 a, i64 b, L lx, i64 l = 0, i64 r = -1, i64 k = 0) {
    if(r < 0) r = n;
    eval(l, r, k);
    if(b <= l || r <= a) return;
    else if(a <= l && r <= b) {
      lazy[k] = lazy_ope(lazy[k], lx);
      flag[k] = true;
      eval(l, r, k);
    }
    else {
      update(a, b, lx, l, (l + r) / 2, k * 2 + 1);
      update(a, b, lx, (l + r) / 2, r, k * 2 + 2);
      node[k] =ope(node[k * 2 + 1], node[k * 2 + 2]);
    }
  }
  
  /* the sum of a[i] for i in [a, b) */
  T get(i64 a, i64 b, i64 l = 0, i64 r = -1, i64 k = 0) {
    if(r < 0) r = n;
    eval(l, r, k);
    if(b <= l || r <= a) return t_ide();
    else if(a <= l && r <= b) return node[k];
    else return ope(get(a, b, l, (l + r) / 2, k * 2 + 1), get(a, b, (l + r) / 2, r, k * 2 + 2));
  }
};

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 };
  }
  lazy_segment_tree seg(a);

  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.get(l, r).sum + 1 << endl;
    }
  }
}
0