結果

問題 No.749 クエリ全部盛り
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-01-22 09:55:31
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 864 ms / 3,000 ms
コード長 3,932 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 108,732 KB
実行使用メモリ 94,348 KB
最終ジャッジ日時 2023-09-03 22:50:52
合計ジャッジ時間 6,431 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 5 ms
4,376 KB
testcase_06 AC 5 ms
4,376 KB
testcase_07 AC 5 ms
4,376 KB
testcase_08 AC 5 ms
4,376 KB
testcase_09 AC 5 ms
4,380 KB
testcase_10 AC 47 ms
5,628 KB
testcase_11 AC 47 ms
5,896 KB
testcase_12 AC 48 ms
6,668 KB
testcase_13 AC 47 ms
6,008 KB
testcase_14 AC 47 ms
5,168 KB
testcase_15 AC 864 ms
93,240 KB
testcase_16 AC 806 ms
94,212 KB
testcase_17 AC 824 ms
93,140 KB
testcase_18 AC 848 ms
93,772 KB
testcase_19 AC 845 ms
94,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


enum MO = 10L^^9 + 7;

// x -> a x + b fib(i) + c
alias Trans = Tuple!(long, long, long);

enum IDENTITY = Trans(1, 0, 0);

Trans mul(Trans f, Trans g) {
  // g[0] (f[0] x + f[1] fib(i) + f[2]) + g[1] fib(i) + g[2]
  return Trans((g[0] * f[0]) % MO, (g[0] * f[1] + g[1]) % MO, (g[0] * f[2] + g[2]) % MO);
}

class SegmentTree {
  int n;
  long[] fib, fibSum;
  long[] sum;
  Trans[] add;
  this(int n_) {
    for (n = 2; n < n_; n <<= 1) {}
    fib = new long[n];
    fib[0] = 0;
    fib[1] = 1;
    foreach (i; 2 .. n) {
      fib[i] = (fib[i - 1] + fib[i - 2]) % MO;
    }
    fibSum = new long[n + 1];
    foreach (i; 0 .. n) {
      fibSum[i + 1] = (fibSum[i] + fib[i]) % MO;
    }
    sum = new long[n << 1];
    add = new Trans[n << 1];
    add[] = IDENTITY;
  }
  void transSum(int u, int l, int r, Trans t) {
    sum[u] = (t[0] * sum[u] + t[1] * (fibSum[r] - fibSum[l]) + t[2] * (r - l)) % MO;
    if (sum[u] < 0) {
      sum[u] += MO;
    }
  }
  long query(int u, int l, int r, int a, int b, Trans t) {
    chmax(a, l);
    chmin(b, r);
    if (a >= b) {
      return 0;
    }
    if (a == l && b == r) {
      transSum(u, l, r, t);
      add[u] = mul(add[u], t);
      return sum[u];
    }
    const uL = u << 1;
    const uR = u << 1 | 1;
    const mid = (l + r) >> 1;
    transSum(uL, l, mid, add[u]);
    transSum(uR, mid, r, add[u]);
    add[uL] = mul(add[uL], add[u]);
    add[uR] = mul(add[uR], add[u]);
    add[u] = IDENTITY;
    const resL = query(uL, l, mid, a, b, t);
    const resR = query(uR, mid, r, a, b, t);
    sum[u] = (sum[uL] + sum[uR]) % MO;
    return (resL + resR) % MO;
  }
  long query(int a, int b, Trans t) {
    return query(1, 0, n, a, b + 1, t);
  }
}

int N, Q;
int[] T, L, R;
long[] K;

void main() {
  try {
    for (; ; ) {
      N = readInt();
      Q = readInt();
      T = new int[Q];
      L = new int[Q];
      R = new int[Q];
      K = new long[Q];
      foreach (q; 0 .. Q) {
        T[q] = readInt();
        L[q] = readInt();
        R[q] = readInt();
        K[q] = readLong();
      }
      auto seg = new SegmentTree(N);
      foreach (q; 0 .. Q) {
        switch (T[q]) {
          case 0: {
            const res = seg.query(L[q], R[q], IDENTITY);
            const ans = ((K[q] * res) % MO + MO) % MO;
            writeln(ans);
          } break;
          case 1: {
            // x -> k
            seg.query(L[q], R[q], Trans(0, 0, K[q]));
          } break;
          case 2: {
            // x -> x + k
            seg.query(L[q], R[q], Trans(1, 0, K[q]));
          } break;
          case 3: {
            // x -> k x
            seg.query(L[q], R[q], Trans(K[q], 0, 0));
          } break;
          case 4: {
            // x -> x + k fib(i)
            seg.query(L[q], R[q], Trans(1, K[q], 0));
          } break;
          default: assert(false);
        }
      }
    }
  } catch (EOFException e) {
  }
}
0