結果

問題 No.876 Range Compress Query
ユーザー _____TAB__________TAB_____
提出日時 2020-04-18 21:55:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 3,058 bytes
コンパイル時間 1,117 ms
コンパイル使用メモリ 99,012 KB
実行使用メモリ 11,732 KB
最終ジャッジ日時 2024-10-04 00:24:16
合計ジャッジ時間 4,986 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 3 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 291 ms
9,936 KB
testcase_12 AC 241 ms
8,848 KB
testcase_13 AC 241 ms
9,804 KB
testcase_14 AC 291 ms
9,808 KB
testcase_15 AC 203 ms
10,444 KB
testcase_16 AC 287 ms
11,300 KB
testcase_17 AC 286 ms
11,732 KB
testcase_18 AC 300 ms
11,232 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename T, typename E>
struct LazySegmentTree{
private:
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  int n, height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  T reflect(int k){
    return laz[k] == ei ? dat[k] : g(dat[k],laz[k]);
  }
  void propagate(int k){
    if(laz[k] == ei) return;
    if(k >= n){
      dat[k] = reflect(k);
      laz[k] = ei;
      return;
    }
    laz[k<<1|0] = h(laz[k<<1|0],laz[k]);
    laz[k<<1|1] = h(laz[k<<1|1],laz[k]);
    dat[k] = reflect(k);
    laz[k] = ei;
  }
  void thrust(int k){
    for(int i = height; i >= 0; --i)
      propagate(k>>i);
  }
  void recalc(int k){
    while(k >>= 1){
      dat[k] = f(reflect(k<<1|0),reflect(k<<1|1));
    }
  }
public:
  LazySegmentTree(F f,G g, H h, T ti, E ei) :
    f(f), g(g), h(h), ti(ti), ei(ei) {}
  void build(int n_){
    n = n_;
    height = 2;
    while(n_ >>= 1) ++height;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(const vector<T> &v){
    int n_ = v.size();
    build(n_);
    for(int i = 0; i < n; ++i) dat[n+i]=v[i];
    for(int i = n-1; i >= 0; --i)
      dat[i]=f(dat[i<<1|0],dat[i<<1|1]);
  }
  void update(int l_, int r_, E x){
    if(l_ >= r_) return;
    l_ += n, r_ += n;
    thrust(l_);
    thrust(r_-1);
    for(int l = l_, r = r_;l < r; l >>= 1, r >>= 1){
      if(l&1) laz[l] = h(laz[l],x), ++l;
      if(r&1) --r, laz[r] = h(laz[r],x);
    }
    recalc(l_);
    recalc(r_-1);
  }
  void set_val(int a, T x){
    thrust(a+=n);
    dat[a] = x;
    laz[a] = ei;
    recalc(a);
  }
  T query(int l, int r){
    if(l >= r) return ti;
    l += n;
    r += n;
    thrust(l);
    thrust(r-1);
    T vl = ti, vr = ti;
    for(; 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 value {
  long long l, r, sum;
  value(long long l, long long r, long long sum) :
    l(l), r(r), sum(sum) {}
};

int main(){
  int N, Q;
  cin >> N >> Q;
  vector<value> A;
  for(int i = 0; i < N; ++i){
    long long a;
    cin >> a;
    A.emplace_back(a,a,0);
  }

  using T = value;
  using E = long long;
  T ti(-1,-1,0);
  E ei = 0;

  function<T(T,T)> f = [](T a, T b){
                         if(a.l < 0) return b;
                         if(b.l < 0) return a;
                         return value(a.l,b.r,a.sum+b.sum+(a.r!=b.l));
                       };
  function<T(T,E)> g = [](T a, E b){
                         a.l += b;
                         a.r += b;
                         return a;
                       };
  function<E(E,E)> h = [](E a, E b){
                         return a+b;
                       };

  LazySegmentTree<T,E> st(f,g,h,ti,ei);
  st.build(A);

  while(Q--){
    int t, l, r;
    cin >> t >> l >> r;
    --l;
    if(t == 1){
      long long x;
      cin >> x;
      st.update(l,r,x);
    }else{
      cout << st.query(l,r).sum+1 << "\n";
    }
  }
}
0