結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2019-05-23 19:32:16 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 467 ms / 3,000 ms |
コード長 | 3,258 bytes |
コンパイル時間 | 465 ms |
コンパイル使用メモリ | 32,256 KB |
実行使用メモリ | 38,128 KB |
最終ジャッジ日時 | 2024-09-17 09:51:32 |
合計ジャッジ時間 | 4,210 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include<stdio.h>#include<stdlib.h>#include<stdint.h>#include<inttypes.h>typedef int32_t i32;typedef int64_t i64;const i32 mod = 1000000007;typedef struct trans {i32 a, b, c;} trans;static inline trans merge (trans g, trans f) {trans h;h.a = (i64) g.a * f.a % mod;h.b = ((i64) g.a * f.b + g.b) % mod;h.c = ((i64) g.a * f.c + g.c) % mod;return h;}typedef struct node {trans f;i32 sum;} node;typedef struct {node *a;i32 *fib;i32 bit;i32 size;} segment_tree;segment_tree* new_segment_tree (const i32 n) {i32 k = 0;while ((1 << k) < n) ++k;segment_tree *s = (segment_tree *) calloc (1, sizeof (segment_tree));s->a = (node *) calloc (2 << k, sizeof (node));i32 *fib = (i32 *) calloc ((1 << k) + 1, sizeof (fib));if (k > 0) {fib[1] = 1;for (i32 i = 2; i < (1 << k); ++i) {fib[i] = (fib[i - 1] + fib[i - 2]) % mod;}}for (i32 i = (1 << k) - 1; i >= 0; --i) {fib[i] = (fib[i] + fib[i + 1]) % mod;}s->fib = fib;s->bit = k;s->size = 1 << k;return s;}i32 eval (segment_tree *s, i32 x) {i32 k = 0;while ((x << k) < s->size) ++k;i32 len = 1 << k;i64 ans = (i64) s->a[x].f.a * s->a[x].sum + (i64) len * s->a[x].f.b + (i64) (s->fib[(x << k) - s->size] + mod - s->fib[(x << k) - s->size + len]) *s->a[x].f.c;return ans % mod;}void propagate (segment_tree *s, i32 x) {x += s->size;node *a = s->a;for (i32 i = s->bit, len = s->size >> 1; i > 0; --i, len >>= 1) {i32 y = x >> i;a[2 * y ].f = merge (a[y].f, a[2 * y ].f);a[2 * y + 1].f = merge (a[y].f, a[2 * y + 1].f);a[y].f = (trans) {1, 0, 0};a[y].sum = (eval (s, 2 * y) + eval (s, 2 * y + 1)) % mod;}}void save (segment_tree *s, i32 x) {x += s->size;for (x >>= 1; x > 0; x >>= 1) {s->a[x].sum = (eval (s, 2 * x) + eval (s, 2 * x + 1)) % mod;}}void update (segment_tree *s, i32 l, i32 r, trans f) {propagate (s, l);propagate (s, r - 1);for (i32 x = l + s->size, y = r + s->size; x < y; x >>= 1, y >>= 1) {if (x & 1) {s->a[x].f = merge (f, s->a[x].f);x++;}if (y & 1) {--y;s->a[y].f = merge (f, s->a[y].f);}}save (s, l);save (s, r - 1);}i32 get_sum (segment_tree *s, i32 l, i32 r) {propagate (s, l);propagate (s, r - 1);i64 sum = 0;for (l += s->size, r += s->size; l < r; l >>= 1, r >>= 1) {if (l & 1) sum += eval (s, l++);if (r & 1) sum += eval (s, --r);}return sum % mod;}void run (void) {i32 n, q;scanf ("%" SCNi32 "%" SCNi32, &n, &q);segment_tree *s = new_segment_tree (n);while (q--) {//for (i32 i = 0; i < n; ++i) printf ("%" PRIi32 " ", get_sum (s, i, i + 1)); puts ("");i32 t, l, r, k;scanf ("%" SCNi32 "%" SCNi32 "%" SCNi32 "%" SCNi32, &t, &l, &r, &k);r++;if (t == 0) {i32 ans = (i64) k * get_sum (s, l, r) % mod;printf ("%" PRIi32 "\n", ans);} else if (t == 1) {update (s, l, r, (trans) {0, k, 0});} else if (t == 2) {update (s, l, r, (trans) {1, k, 0});} else if (t == 3) {update (s, l, r, (trans) {k, 0, 0});} else {update (s, l, r, (trans) {1, 0, k});}}}int main (void) {run();return 0;}