結果

問題 No.876 Range Compress Query
ユーザー どららどらら
提出日時 2019-09-07 12:04:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 515 ms / 2,000 ms
コード長 4,951 bytes
コンパイル時間 1,985 ms
コンパイル使用メモリ 178,748 KB
実行使用メモリ 11,328 KB
最終ジャッジ日時 2023-09-08 14:35:57
合計ジャッジ時間 7,558 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 4 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 4 ms
4,376 KB
testcase_04 AC 3 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 4 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 479 ms
11,260 KB
testcase_12 AC 408 ms
11,244 KB
testcase_13 AC 418 ms
11,324 KB
testcase_14 AC 487 ms
11,324 KB
testcase_15 AC 363 ms
11,228 KB
testcase_16 AC 495 ms
11,172 KB
testcase_17 AC 486 ms
11,324 KB
testcase_18 AC 515 ms
11,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

template <class Monoid, class OpMonoid>
class LazySegmentTree {
  using FuncMM = std::function<Monoid(Monoid, Monoid)>;
  using FuncMO = std::function<Monoid(Monoid, OpMonoid, int)>;
  using FuncOO = std::function<OpMonoid(OpMonoid, OpMonoid)>;

  const FuncMM funcMM;
  const FuncMO funcMO;
  const FuncOO funcOO;
  const Monoid monoidIdentity;
  const OpMonoid opMonoidIdentity;

  int N;
  std::vector<Monoid> dat;
  std::vector<OpMonoid> lazy;

  void setLazy(int k, const OpMonoid& om) { lazy[k] = funcOO(lazy[k], om); }
  void push(int k, int len) {
    if (lazy[k] == opMonoidIdentity) return;
    if (k < N) {
      setLazy(2 * k + 0, lazy[k]);
      setLazy(2 * k + 1, lazy[k]);
    }
    dat[k] = funcMO(dat[k], lazy[k], len);
    lazy[k] = opMonoidIdentity;
  }

 public:
  LazySegmentTree(int n, const FuncMM funcMM, const FuncMO funcMO,
                  const FuncOO funcOO, const Monoid monoidIdentity,
                  const OpMonoid opMonoidIdentity)
      : funcMM(funcMM),
        funcMO(funcMO),
        funcOO(funcOO),
        monoidIdentity(monoidIdentity),
        opMonoidIdentity(opMonoidIdentity) {
    N = 1;
    while (N < n) N *= 2;
    dat.resize(2 * N, monoidIdentity);
    lazy.resize(2 * N, opMonoidIdentity);
  }

  void dump() {
    std::cout << "dat: ";
    for (int i = 1; i < dat.size(); i++) {
      if (i == N) std::cout << "| ";
      std::cout << dat[i].ai << "(" << lazy[i].p << "," << lazy[i].q << ","
                << lazy[i].r << ") ";
    }
    std::cout << std::endl;
  }

  void set(int i, const Monoid& v) { dat[N + i] = v; }

  void init() {
    for (int i = N - 1; i > 0; i--) {
      dat[i] = funcMM(dat[2 * i + 0], dat[2 * i + 1]);
    }
  }

  void update(int s, int t, const OpMonoid& om) { update(s, t, om, 1, 0, N); }
  void update(int s, int t, const OpMonoid& om, int k, int l, int r) {
    push(k, r - l);
    if (r <= s || t <= l) return;
    if (s <= l && r <= t) {
      setLazy(k, om);
      push(k, r - l);
      return;
    }
    update(s, t, om, 2 * k + 0, l, (l + r) / 2);
    update(s, t, om, 2 * k + 1, (l + r) / 2, r);
    dat[k] = funcMM(dat[2 * k + 0], dat[2 * k + 1]);
  }

  Monoid query(int s, int t) { return query(s, t, 1, 0, N); }
  Monoid query(int s, int t, int k, int l, int r) {
    push(k, r - l);
    if (r <= s || t <= l) return monoidIdentity;
    if (s <= l && r <= t) return dat[k];
    Monoid vl = query(s, t, 2 * k + 0, l, (l + r) / 2);
    Monoid vr = query(s, t, 2 * k + 1, (l + r) / 2, r);
    return funcMM(vl, vr);
  }
};

struct VAL {
  ll a;
};

struct OP {
  ll x;
};
bool operator==(const OP& a, const OP& b) {
  return a.x == b.x;
}

int main(){
  int N, Q;
  cin >> N >> Q;

  auto funcMM = [](const VAL& a, const VAL& b) {
    VAL ret;
    ret.a = a.a + b.a;
    return ret;
  };
  auto funcMO = [](const VAL& a, const OP& b, int k) {
    VAL ret;
    ret.a = a.a + b.x * k;
    return ret;
  };
  auto funcOO = [](const OP& a, const OP& b) {
    OP ret;
    ret.x = a.x + b.x;
    return ret;
  };

  LazySegmentTree<VAL, OP> lst1(N, funcMM, funcMO, funcOO, (VAL){0}, (OP){0});
  LazySegmentTree<VAL, OP> lst2(N, funcMM, funcMO, funcOO, (VAL){0}, (OP){0});

  rep(i,N){
    ll a;
    cin >> a;
    lst1.update(i,i+1,(OP){a});
  }
  rep(i,N-1){
    VAL x = lst1.query(i,i+1);
    VAL y = lst1.query(i+1,i+2);
    if(x.a == y.a){
      lst2.update(i,i+1,(OP){0});
    }else{
      lst2.update(i,i+1,(OP){1});
    }
  }

  
  rep(i,Q){
    int t, l, r, x;
    cin >> t;
    if(t == 1){
      cin >> l >> r >> x;
      l--;
      r--;
      
      lst1.update(l,r+1,(OP){x});
      if(l>0){
        VAL ll = lst1.query(l-1,l);
        VAL lll = lst1.query(l,l+1);
        VAL z = lst2.query(l-1,l);
        if(ll.a == lll.a){
          if(z.a == 1){
            lst2.update(l-1,l,(OP){-1});
          }
        }else{
          if(z.a == 0){
            lst2.update(l-1,l,(OP){1});
          }
        }
      }
      if(r<N-1){
        VAL rr = lst1.query(r,r+1);
        VAL rrr = lst1.query(r+1,r+2);
        VAL z = lst2.query(r,r+1);
        if(rr.a == rrr.a){
          if(z.a == 1){
            lst2.update(r,r+1,(OP){-1});
          }
        }else{
          if(z.a == 0){
            lst2.update(r,r+1,(OP){1});
          }
        }
      }
    }else{
      cin >> l >> r;
      l--;
      r--;
      /*
      rep(i,N){
        VAL z = lst1.query(i,i+1);
        cout << " " << z.a;
      }
      cout << endl;
      cout << " ";
      rep(i,N-1){
        VAL z = lst2.query(i,i+1);
        cout << " " << z.a;
      }
      cout << endl;
      */
      VAL z = lst2.query(l,r);
      cout << z.a+1 << endl;
    }
  }
  
  return 0;
}
0