Submit Info #54525

Problem Lang User Status Time Memory
Range Affine Range Sum csharp (anonymous) AC 2623 ms 78.95 MiB

ケース詳細
Name Status Time Memory
example_00 AC 79 ms 4.58 MiB
max_random_00 AC 2564 ms 78.95 MiB
max_random_01 AC 2553 ms 78.95 MiB
max_random_02 AC 2623 ms 78.95 MiB
random_00 AC 2072 ms 74.96 MiB
random_01 AC 2213 ms 77.70 MiB
random_02 AC 1161 ms 24.33 MiB
small_00 AC 75 ms 5.20 MiB
small_01 AC 67 ms 5.22 MiB
small_02 AC 82 ms 5.21 MiB
small_03 AC 68 ms 5.21 MiB
small_04 AC 82 ms 5.21 MiB
small_05 AC 70 ms 5.21 MiB
small_06 AC 74 ms 5.18 MiB
small_07 AC 75 ms 5.20 MiB
small_08 AC 71 ms 5.22 MiB
small_09 AC 74 ms 5.21 MiB
small_random_00 AC 73 ms 5.46 MiB
small_random_01 AC 87 ms 5.33 MiB

using System; using System.Collections.Generic; class Program { Input ip; int n, q; int[] a; const int p = 998244353; void Input() { n = ip.Int(); q = ip.Int(); a = new int[n]; for (var i = 0; i < n; i++) { a[i] = ip.Int(); } } void Solve() { int zero = 0; (int b, int c) zeroLazy = (1, 0); int Merge(int x, int y) => (x + y) % p; (int b, int c) MergeLazy((int b, int c) x, (int b, int c) y) { long xB = x.b; long xC = x.c; long yB = y.b; long yC = y.c; return ((int)(xB * yB % p), (int)((xC * yB + yC) % p)); } int EvaluateLazy(int x, int impact, (int b, int c) y) { long X = x; long B = y.b; long C = y.c; return (int)((X * B + C * impact) % p); } var tree = new LazySegmentTree<int, (int b, int c)>( a, zero, zeroLazy, Merge, MergeLazy, EvaluateLazy ); var answers = new List<int>(); for (var i = 0; i < q; i++) { var type = ip.Int(); var l = ip.Int(); var r = ip.Int(); if (type == 0) { var b = ip.Int(); var c = ip.Int(); tree.Update(l, r, (b, c)); } else { answers.Add(tree.Query(l, r)); } } foreach (var ans in answers) Output(ans); } void Output(object x) => Console.WriteLine(x); public static void DebugWL(object x) => System.Diagnostics.Debug.WriteLine(x); public static void Main() => new Program().Answer(); void Answer() { ip = new Input(); Input(); Solve(); } } class Input { string[] input; int iter; public Input() { input = new string[0]; iter = 0; } public string String() { if (iter >= input.Length) { input = Console.ReadLine().Split(' '); iter = 0; } return input[iter++]; } public int Int() => int.Parse(String()); public long Long() => long.Parse(String()); } // SegmentTree<T, U> // T Query(int a, int b): // return the value f([a, b)) // void Update(int a, int b, U c): // change the value of [a, b) with c public class LazySegmentTree<T, U> { int baseSize; (T value, int impact, U lazy)[] tree; T zero; U zeroLazy; Func<T, T, T> Merge; Func<U, U, U> MergeLazy; Func<T, int, U, T> EvaluateLazy; public LazySegmentTree( T[] input, T zero, U zeroLazy, Func<T, T, T> Merge, Func<U, U, U> MergeLazy, Func<T, int, U, T> EvaluateLazy ) { this.zero = zero; this.zeroLazy = zeroLazy; this.Merge = Merge; this.MergeLazy = MergeLazy; this.EvaluateLazy = EvaluateLazy; Initialize(input); } void Initialize(T[] input) { baseSize = 1; while (baseSize < input.Length) baseSize = baseSize << 1; tree = new (T value, int impact, U lazy)[baseSize * 2 - 1]; for (var i = baseSize * 2 - 2; i > -1; i--) { tree[i].impact = i < baseSize - 1 ? tree[i * 2 + 1].impact * 2 : 1; tree[i].value = zero; tree[i].lazy = zeroLazy; } for (var i = 0; i < input.Length; i++) { tree[baseSize - 1 + i].value = input[i]; Update(i, i + 1, zeroLazy); } } public T Query(int a, int b) { return Query(a, b, 0, 0, baseSize); } T Query(int a, int b, int index, int l, int r) { if (b <= l || r <= a) return zero; Descend(index); if (a <= l && r <= b) return tree[index].value; var vl = Query(a, b, index * 2 + 1, l, (l + r) / 2); var vr = Query(a, b, index * 2 + 2, (l + r) / 2, r); return Merge(vl, vr); } public void Update(int a, int b, U c) { Update(a, b, c, 0, 0, baseSize); } void Update(int a, int b, U c, int index, int l, int r) { if (a <= l && r <= b) { tree[index].lazy = MergeLazy(tree[index].lazy, c); Descend(index); return; } Descend(index); if (b <= l || r <= a) return; Update(a, b, c, index * 2 + 1, l, (l + r) / 2); Update(a, b, c, index * 2 + 2, (l + r) / 2, r); tree[index].value = Merge(tree[index * 2 + 1].value, tree[index * 2 + 2].value); } void Descend(int index) { var node = tree[index]; tree[index].value = EvaluateLazy(node.value, node.impact, node.lazy); if (index < baseSize - 1) { tree[index * 2 + 1].lazy = MergeLazy(tree[index * 2 + 1].lazy, node.lazy); tree[index * 2 + 2].lazy = MergeLazy(tree[index * 2 + 2].lazy, node.lazy); } tree[index].lazy = zeroLazy; } }