結果

問題 No.749 クエリ全部盛り
ユーザー tnakao0123tnakao0123
提出日時 2018-10-25 19:29:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,441 ms / 3,000 ms
コード長 4,640 bytes
コンパイル時間 1,141 ms
コンパイル使用メモリ 101,764 KB
実行使用メモリ 103,748 KB
最終ジャッジ日時 2023-08-12 07:10:12
合計ジャッジ時間 10,248 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,684 KB
testcase_01 AC 2 ms
7,608 KB
testcase_02 AC 2 ms
7,664 KB
testcase_03 AC 2 ms
7,620 KB
testcase_04 AC 2 ms
7,716 KB
testcase_05 AC 7 ms
7,624 KB
testcase_06 AC 6 ms
7,644 KB
testcase_07 AC 6 ms
7,648 KB
testcase_08 AC 6 ms
7,648 KB
testcase_09 AC 6 ms
7,904 KB
testcase_10 AC 62 ms
8,112 KB
testcase_11 AC 62 ms
7,908 KB
testcase_12 AC 61 ms
7,904 KB
testcase_13 AC 62 ms
7,924 KB
testcase_14 AC 62 ms
7,920 KB
testcase_15 AC 1,422 ms
103,456 KB
testcase_16 AC 1,413 ms
103,544 KB
testcase_17 AC 1,441 ms
103,540 KB
testcase_18 AC 1,422 ms
103,648 KB
testcase_19 AC 1,421 ms
103,748 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 749.cc:  No.749 クエリ全部盛り - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 1000000;
const int MAX_E2 = 1 << 21; // = 2097152
const int D = 3;
const int MOD = 1000000007;

/* typedef */

typedef long long ll;
typedef int vec[D];
typedef vec mat[D];

inline void initmat(mat a);
inline void unitmat(mat a);
inline void copymat(const mat a, mat b);
inline void mulmat(const mat a, const mat b, mat c);
inline void mulmatvec(const mat a, const vec b, vec c);

template <typename T, const int MAX_E2>
struct SegTreeFibo {
  int n, e2, ls[MAX_E2];
  T as[MAX_E2], fs[MAX_E2];
  bool dfs[MAX_E2];
  mat ms[MAX_E2];
  SegTreeFibo() {}

  void init(int _n) {
    n = _n;
    for (e2 = 1; e2 < n; e2 <<= 1);

    fs[e2 - 1 + 0] = 0, fs[e2 - 1 + 1] = 1;
    for (int i = 2, j = e2 - 1 + i; i < n; i++, j++)
      fs[j] = (fs[j - 1] + fs[j - 2]) % MOD;
    for (int i = 0; i < e2; i++) ls[e2 - 1 + i] = 1;

    for (int i = e2 - 2; i >= 0; i--) {
      int i1 = i * 2 + 1, i2 = i1 + 1;
      fs[i] = (fs[i1] + fs[i2]) % MOD;
      ls[i] = ls[i1] + ls[i2];
    }

    for (int i = e2 - 2 + n; i >= 0; i--) unitmat(ms[i]);
  }

  T get(int i) { return as[e2 - 1 + i]; }

  void op_delegate(int k, int k1) {
    mat m1;
    vec v0, v1;
    v0[0] = as[k1], v0[1] = fs[k1], v0[2] = ls[k1];
    mulmatvec(ms[k], v0, v1);
    as[k1] = v1[0];
    mulmat(ms[k], ms[k1], m1);
    copymat(m1, ms[k1]);
    dfs[k1] = true;
  }
  
  void op_range(int r0, int r1, mat m, int k, int i0, int i1) {
    if (r1 <= i0 || i1 <= r0) return;

    mat m1;
    vec v0, v1;

    if (r0 <= i0 && i1 <= r1) {
      v0[0] = as[k], v0[1] = fs[k], v0[2] = ls[k];
      mulmatvec(m, v0, v1);
      as[k] = v1[0];
      mulmat(m, ms[k], m1);
      copymat(m1, ms[k]);
      dfs[k] = true;
      return;
    }

    int k1 = k * 2 + 1, k2 = k1 + 1;
    if (dfs[k]) {
      op_delegate(k, k1);
      op_delegate(k, k2);
      unitmat(ms[k]);
      dfs[k] = false;
    }

    int im = (i0 + i1) / 2;
    op_range(r0, r1, m, k1, i0, im);
    op_range(r0, r1, m, k2, im, i1);
    as[k] = (as[k1] + as[k2]) % MOD;
  }
  void op_range(int r0, int r1, mat m) { op_range(r0, r1, m, 0, 0, e2); }

  T sum_range(int r0, int r1, int k, int i0, int i1) {
    if (r1 <= i0 || i1 <= r0) return 0;
    if (r0 <= i0 && i1 <= r1) return as[k];

    int k1 = k * 2 + 1, k2 = k1 + 1;
    if (dfs[k]) {
      op_delegate(k, k1);
      op_delegate(k, k2);
      unitmat(ms[k]);
      dfs[k] = false;
    }
    
    int im = (i0 + i1) / 2;
    T v0 = sum_range(r0, r1, k1, i0, im);
    T v1 = sum_range(r0, r1, k2, im, i1);
    return (v0 + v1) % MOD;
  }

  T sum_range(int r0, int r1) {
    return sum_range(r0, r1, 0, 0, e2);
  }
};

/* global variables */

SegTreeFibo<int,MAX_E2> st;

/* subroutines */

inline void initmat(mat a) { memset(a, 0, sizeof(mat)); }
inline void unitmat(mat a) {
  initmat(a);
  for (int i = 0; i < D; i++) a[i][i] = 1;
}

inline void copymat(const mat a, mat b) { memcpy(b, a, sizeof(mat)); }

inline void mulmat(const mat a, const mat b, mat c) {
  for (int i = 0; i < D; i++)
    for (int j = 0; j < D; j++) {
      c[i][j] = 0;
      for (int k = 0; k < D; k++)
        c[i][j] = (c[i][j] + (ll)a[i][k] * b[k][j] % MOD) % MOD;
    }
}

inline void mulmatvec(const mat a, const vec b, vec c) {
  for (int i = 0; i < D; i++) {
    c[i] = 0;
    for (int j = 0; j < D; j++)
      c[i] = (c[i] + (ll)a[i][j] * b[j] % MOD) % MOD;
  }
}

/* main */

int main() {
  int n, qn;
  scanf("%d%d", &n, &qn);

  st.init(n);

  while (qn--) {
    int q, l, r, k;
    scanf("%d%d%d%d", &q, &l, &r, &k);
    r++;

    if (q == 0) {
      int sum = st.sum_range(l, r);
      printf("%lld\n", (ll)sum * k % MOD);
    }
    else {
      mat m;
      unitmat(m);
      switch (q) {
	// 1: ai = k
      case 1: m[0][0] = 0, m[0][2] = k; break;
	// 2: ai = ai + k
      case 2: m[0][2] = k; break;
	// 3: ai = ai * k
      case 3: m[0][0] = k; break;
	// 4: ai = ai + k * fi
      case 4: m[0][1] = k; break;
      }

      st.op_range(l, r, m);

      /*
      for (int i = 0; i < st.e2 - 1; i++) {
	int i1 = 2 * i + 1, i2 = i1 + 1;
	st.op_delegate(i, i1);
	st.op_delegate(i, i2);
      }
      for (int i = 0; i < st.e2 * 2 - 1; i++) printf("%d ", st.as[i]);
      putchar('\n');
      */
    }
  }

  return 0;
}
0