結果

問題 No.749 クエリ全部盛り
ユーザー どららどらら
提出日時 2018-10-31 21:50:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 896 ms / 3,000 ms
コード長 4,506 bytes
コンパイル時間 1,934 ms
コンパイル使用メモリ 181,140 KB
実行使用メモリ 85,232 KB
最終ジャッジ日時 2024-11-19 13:40:10
合計ジャッジ時間 7,656 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 5 ms
6,820 KB
testcase_06 AC 5 ms
6,824 KB
testcase_07 AC 5 ms
6,816 KB
testcase_08 AC 5 ms
6,820 KB
testcase_09 AC 5 ms
6,816 KB
testcase_10 AC 42 ms
6,820 KB
testcase_11 AC 42 ms
6,816 KB
testcase_12 AC 41 ms
6,820 KB
testcase_13 AC 42 ms
6,816 KB
testcase_14 AC 41 ms
6,816 KB
testcase_15 AC 873 ms
85,232 KB
testcase_16 AC 876 ms
85,116 KB
testcase_17 AC 872 ms
85,112 KB
testcase_18 AC 876 ms
85,124 KB
testcase_19 AC 896 ms
85,124 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;

#define MOD 1000000007

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 ai;
  ll fi;
};

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

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

  auto funcMM = [](VAL a, VAL b) {
    VAL ret;
    ret.ai = (a.ai + b.ai) % MOD;
    ret.fi = (a.fi + b.fi) % MOD;
    return ret;
  };
  auto funcMO = [](VAL a, OP b, int k) {
    VAL ret;
    ret.ai = ((a.ai * b.p) % MOD + (a.fi * b.q) % MOD + b.r * k) % MOD;
    ret.fi = a.fi;
    return ret;
  };
  auto funcOO = [](OP a, OP b) {
    OP ret;
    ret.p = (b.p * a.p) % MOD;
    ret.q = ((b.p * a.q) % MOD + b.q) % MOD;
    ret.r = ((b.p * a.r) % MOD + b.r) % MOD;
    return ret;
  };

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

  ll a = 0, b = 1;
  lst.set(0, (VAL){0, a});
  lst.set(1, (VAL){0, b});
  REP(i, 2, N) {
    ll c = (a + b) % MOD;
    lst.set(i, (VAL){0, c});
    a = b;
    b = c;
  }
  lst.init();

  rep(qn, Q) {
    ll q, l, r, k;
    cin >> q >> l >> r >> k;
    r++;
    if (q == 0) {
      std::cout << (k * (ll)lst.query(l, r).ai) % MOD << std::endl;
    } else if (q == 1) {
      OP op;
      op.p = 0;
      op.q = 0;
      op.r = k;
      lst.update(l, r, op);
    } else if (q == 2) {
      OP op;
      op.p = 1;
      op.q = 0;
      op.r = k;
      lst.update(l, r, op);
    } else if (q == 3) {
      OP op;
      op.p = k;
      op.q = 0;
      op.r = 0;
      lst.update(l, r, op);
    } else if (q == 4) {
      OP op;
      op.p = 1;
      op.q = k;
      op.r = 0;
      lst.update(l, r, op);
    }
  }

  return 0;
}
0