問題の趣旨
区画 i の標高を E[i] とするとき、不便さを |E[1] – E[2]| + |E[2] – E[3]| + … + |E[N-1] – E[N]| と定義する。i回目の地殻変動では、区画[L[i], R[i]]の標高がV[i]だけ変化するが、各地殻変動後の不便さをそれぞれ求めよ。
地殻変動がおきたとき隣の区画との高低差が変動するのは区画[l, r]の内部と外部の境界線だけです。そこでその差分を計算すればよいのですが、ここはあえて遅延評価型のセグメント木で解いてみることにします。
Contents
セグメント木で絶対値をどう扱うか？
セグメント木では要素をふたつずつ組み合わせて計算をしていきます。そのためノードを定義して各ノードがカバーする区間の不便さ（隣り合う区間の差の絶対値の総和）と両端の標高を管理する必要があります。
Node構造体の定義
まずNode構造体を定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
public class RangeAbsSumDiffQuery { struct Node { public long Left = 0; // ノードがカバーする区間の左端の値 public long Right = 0; // ノードがカバーする区間の右端の値 public long AbsSum = 0; // ノードがカバーする区間内の隣り合う区画の差の絶対値の総和 public int Length = 0; // ノードがカバーする区間の長さ public Node(long left, long right, long absSum, int length) { Left = left; Right = right; AbsSum = absSum; Length = length; } public Node(long value) { Left = value; Right = value; AbsSum = 0; Length = 1; } public Node() { Length = 0; } } } |
LazySegtreeOperator構造体の定義
LazySegtreeクラスの型引数として渡す構造体を定義します。
単位元は長さ0です。作用の単位元 FIdentity は 0 です。地殻変動同士が重なった場合は単純にそれらを加算すればよいので Composition(long nf, long cf) は nf + cf です。また地殻変動がおきたときはノードがカバーする区間の両端の値に変動量を加算すればよいので、Mapping(long f, Node x) は x.Left += f; x.Right += f;です。
Operate(Node x, Node y) ではノードがカバーする区間の両端、隣り合う区間の差の絶対値の総和（Math.Abs(x.Right – y.Left)とすでに計算されている絶対値の総和の合計）、区間の長さで新しいNodeオブジェクトを生成して返しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public class RangeAbsSumDiffQuery { struct LazySegtreeOperator : ILazySegtreeOperator<Node, long> { public Node Identity => new Node(); // 単位元 long ILazySegtreeOperator<Node, long>.FIdentity => 0; // 作用の単位元 long ILazySegtreeOperator<Node, long>.Composition(long nf, long cf) => nf + cf; Node ILazySegtreeOperator<Node, long>.Mapping(long f, Node x) { x.Left += f; x.Right += f; return x; } public Node Operate(Node x, Node y) { if (x.Length > 0 && y.Length > 0) return new Node(x.Left, y.Right, Math.Abs(x.Right - y.Left) + x.AbsSum + y.AbsSum, x.Length + y.Length); else if (x.Length > 0) return x; else if (y.Length > 0) return y; else return new Node(); } } } |
コンストラクタ
コンストラクタは以下のとおりです。LazySegtreeオブジェクトを生成して引数の配列の値をセットしています。
|
1 2 3 4 5 6 7 8 9 10 11 |
public class RangeAbsSumDiffQuery { int N = 0; LazySegtree<Node, long, LazySegtreeOperator> seg; public RangeAbsSumDiffQuery(long[] arr) { N = arr.Length; seg = new LazySegtree<Node, long, LazySegtreeOperator>(arr.Select(_ => new Node(_)).ToArray()); } } |
区間に値を加算する
区間に値を加算する処理を示します。
|
1 2 3 4 |
public class RangeAbsSumDiffQuery { public void Add(int left, int right, long v) => seg.Apply(left, right + 1, v); } |
区間の総和を計算する
区間の総和を計算する処理を示します。
|
1 2 3 4 5 6 7 8 |
public class RangeAbsSumDiffQuery { // 閉区間 [left, right]の総和を求める public long Sum(int left, int right) => seg.Prod(left, right + 1).AbsSum; // 全体の総和を求める public long Sum() => seg.AllProd.AbsSum; } |
要素に値を設定したり取得する処理を示します。
|
1 2 3 4 5 6 7 8 |
public class RangeAbsSumDiffQuery { public long this[int idx] { get => seg[idx].Left; set => seg[idx] = new Node(value); } } |
RangeAbsSumDiffQueryクラスを使ってみる
定義したRangeAbsSumDiffQueryクラスを用いて解を出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Program { static void Main() { int[] ReadIntArray() => ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); long[] ReadLongArray() => ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); int[] vs1 = ReadIntArray(); int N = vs1[0]; int Q = vs1[1]; long[] A = ReadLongArray(); RangeAbsSumDiffQuery seg = new RangeAbsSumDiffQuery(A); List<long> ans = new List<long>(); for (int i = 0; i < Q; i++) { int[] vs2 = ReadIntArray(); int left = vs2[0]; int right = vs2[1]; long v = vs2[2]; seg.Add(left - 1, right - 1, v); // 入力が 1-indexed なので-1している ans.Add(seg.Sum()); } foreach (long v in ans) Console.WriteLine(v); } } |
