結果

問題 No.749 クエリ全部盛り
ユーザー 0w10w1
提出日時 2018-10-20 11:49:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 625 ms / 3,000 ms
コード長 4,961 bytes
コンパイル時間 2,890 ms
コンパイル使用メモリ 234,804 KB
実行使用メモリ 112,128 KB
最終ジャッジ日時 2024-11-19 02:18:04
合計ジャッジ時間 6,969 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 4 ms
5,248 KB
testcase_08 AC 4 ms
5,248 KB
testcase_09 AC 4 ms
5,248 KB
testcase_10 AC 27 ms
5,248 KB
testcase_11 AC 28 ms
5,248 KB
testcase_12 AC 27 ms
5,248 KB
testcase_13 AC 26 ms
5,248 KB
testcase_14 AC 27 ms
5,248 KB
testcase_15 AC 584 ms
112,000 KB
testcase_16 AC 566 ms
112,128 KB
testcase_17 AC 568 ms
111,976 KB
testcase_18 AC 560 ms
112,120 KB
testcase_19 AC 625 ms
112,128 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename D>
struct Segt {
  D zero;
  int length;
  vector<D> dat;
  function<D(D, D)> fpull;
  function<void(D&, D&, D&)> fpush;
  Segt(const vector<D> &d, D z, const function<D(D, D)> fl, function<void(D&, D&, D&)> fh)
      : zero(z), length(d.size()), fpull(fl), fpush(fh) {
    function<void(int, int, int)> build = [&](int t, int lb, int rb) {
      if (rb - lb == 1) return void(dat[t] = d[lb]);
      int mb = lb + rb >> 1;
      build(t << 1, lb, mb);
      build(t << 1 | 1, mb, rb);
      dat[t] = fpull(dat[t << 1], dat[t << 1 | 1]);
    };
    int n = 1 << 33 - __builtin_clz(d.size());
    dat.resize(n);
    build(1, 0, length);
  }
  void modify(int ql, int qr, const D &v) {
    function<void(int, int, int)> _modify = [&](int t, int lb, int rb) {
      if (qr <= lb || rb <= ql) return;
      if (ql <= lb && rb <= qr) return fpush(dat[0] = v, dat[t], dat[0]);
      fpush(dat[t], dat[t << 1], dat[t << 1 | 1]);
      int mb = lb + rb >> 1;
      _modify(t << 1, lb, mb);
      _modify(t << 1 | 1, mb, rb);
      dat[t] = fpull(dat[t << 1], dat[t << 1 | 1]);
    };
    _modify(1, 0, length);
  }
  D query(int ql, int qr) {
    function<D(int, int, int)> _query = [&](int t, int lb, int rb) {
      if (qr <= lb || rb <= ql) return zero;
      if (ql <= lb && rb <= qr) return dat[t];
      fpush(dat[t], dat[t << 1], dat[t << 1 | 1]);
      int mb = lb + rb >> 1;
      D a = (_query(t << 1, lb, mb));
      D b = (_query(t << 1 | 1, mb, rb));
      return fpull(a, b);//_query(t << 1, lb, mb), _query(t << 1 | 1, mb, rb));
    };
    return _query(1, 0, length);
  }
  void print(int t = 1) {
    return;
    if (t << 1 < dat.size()) print(t << 1);
    cout << "dat[" << t << "] = ";
    cout << get<0>(dat[t]) << " ";
    cout << get<1>(dat[t]) << " ";
    cout << get<2>(dat[t]) << " ";
    cout << get<3>(dat[t]) << " ";
    cout << get<4>(dat[t]) << " ";
    cout << get<5>(dat[t]) << " ";
    cout << get<6>(dat[t]) << " ";
    cout << get<7>(dat[t]) << "\n";
    if ((t << 1 | 1) < dat.size()) print(t << 1 | 1);
  }
};

const int MOD = int(1e9 + 7);

signed main() {
  ios::sync_with_stdio(false);

  int N, Q;
  cin >> N >> Q;

  vector<int> _fib(N);
  for (int i = _fib[1] = 1; i + 1 < N; ++i) _fib[i + 1] = (_fib[i - 1] + _fib[i]) % MOD;
  Segt<int> fib(_fib, 0, [&](int a, int b) { return (a + b) % MOD; },
                [](int &f, int &l, int &r) {});

               // sum, add, mul, adc, siz, set, st?, idx
  using D = tuple<int, int, int, int, int, int, int, int>;

  auto fpull = [&](D a, D b) {
    return D((get<0>(a) + get<0>(b)) % MOD, 0, 1, 0, get<4>(a) + get<4>(b), 0, 0, get<7>(a) / 2);
  };
  auto fpush = [&](D &f, D &l, D &r) {
    int lsum, ladd, lmul, ladc, lsize, lset, lbset, lx;
    int rsum, radd, rmul, radc, rsize, rset, rbset, rx;
    int fsum, fadd, fmul, fadc, fsize, fset, fbset, fx;
    tie(lsum, ladd, lmul, ladc, lsize, lset, lbset, lx) = l;
    tie(rsum, radd, rmul, radc, rsize, rset, rbset, rx) = r;
    tie(fsum, fadd, fmul, fadc, fsize, fset, fbset, fx) = f;
    if (fbset) {
      l = D(1LL * lsize * fset % MOD, 0, 1, 0, lsize, fset, 1, lx);
      r = D(1LL * rsize * fset % MOD, 0, 1, 0, rsize, fset, 1, rx);
    } {
      tie(lsum, ladd, lmul, ladc, lsize, lset, lbset, lx) = l;
      tie(rsum, radd, rmul, radc, rsize, rset, rbset, rx) = r;
      l = D((1LL * lsum * fmul % MOD +
             1LL * fadd * lsize % MOD + 
             1LL * fadc * fib.dat[lx] % MOD) % MOD,
            (1LL * ladd * fmul + fadd) % MOD, 1LL * lmul * fmul % MOD,
            (1LL * ladc * fmul + fadc) % MOD, lsize, lset, lbset, lx);
      r = D((1LL * rsum * fmul % MOD +
             1LL * fadd * rsize % MOD +
             1LL * fadc * fib.dat[rx] % MOD) % MOD,
            (1LL * radd * fmul + fadd) % MOD, 1LL * rmul * fmul % MOD,
            (1LL * radc * fmul + fadc) % MOD, rsize, rset, rbset, rx);
    }
    f = D(fsum, 0, 1, 0, fsize, 0, 0, fx);
  };

  vector<D> dat(N);
  for (int i = 0; i < N; ++i) dat[i] = D(0, 0, 1, 0, 1, 0, 0, -1); {
    function<void(int, int, int)> write_index = [&](int t, int lb, int rb) {
      if (rb - lb == 1) return void(get<7>(dat[lb]) = t);
      write_index(t << 1, lb, lb + rb >> 1);
      write_index(t << 1 | 1, lb + rb >> 1, rb);
    };
    write_index(1, 0, N);
  }
  Segt<D> tree(dat, D(0, 0, 1, 0, 1, 0, 0, -1), fpull, fpush);
  tree.print();

  for (int i = 0; i < Q; ++i) {
    int q, l, r, k;
    cin >> q >> l >> r >> k;
    if (q == 0) {
      cout << (1LL * get<0>(tree.query(l, r + 1)) * k % MOD + MOD) % MOD << '\n';
    } else if (q == 1) {
      tree.modify(l, r + 1, D(0, 0, 1, 0, 0, k, 1, -1));
    } else if (q == 2) {
      tree.modify(l, r + 1, D(0, k, 1, 0, 0, 0, 0, -1));
    } else if (q == 3) {
      tree.modify(l, r + 1, D(0, 0, k, 0, 0, 0, 0, -1));
    } else if (q == 4) {
      tree.modify(l, r + 1, D(0, 0, 1, k, 0, 0, 0, -1));
    }
    tree.print();
  }

  return 0;
}
0