ac-library-csharpを使ってみるの続きです。今回はセグメント木編です。自分でセグメント木を実装するのは難しいのでac-library-csharpに頼りましょう（おいおい）。
セグメント木
AtCoder.Segtreeクラスではノードの演算と単位元を定義しなければなりません。これはISegtreeOperatorを継承した構造体でおこないます。区間の最大値を求めるので単位元はMinValue、二項演算の結果は値が大きいほうを返せばよいでしょう。
次に X[i] ≦ j ≦ N であり V[i] ≦ A[j] を満たす最小の j を求める方法ですが、これは二分探索法を用います。区間 [X[i], N) のなかから A の最大値が V[i] 以上になるような 最小の j を求め、1-indexedで出力するので j に 1 を加えた値を出力すればよいです。このような値が見つからない場合は N + 1 を出力します。
|
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); AtCoder.Segtree<long, SegtreeOperator> segtree = new AtCoder.Segtree<long, SegtreeOperator>(N); for (int i = 0; i < N; i++) segtree[i] = A[i]; for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; if (t == 1) { int x = vs[1] - 1; // 1-indexed -> 0-indexed int v = vs[2]; segtree[x] = v; } if (t == 2) { int l = vs[1] - 1; // 1-indexed -> 0-indexed int r = vs[2]; Console.WriteLine(segtree.Prod(l, r)); } if (t == 3) { int x = vs[1] - 1; int v = vs[2]; int ans = AtCoder.StlFunction.BinarySearch(N, x - 1, _ => segtree.Prod(x, _ + 1) >= v); Console.WriteLine(ans + 1); // 0-indexed -> 1-indexed } } } struct SegtreeOperator : ISegtreeOperator<long> { long ISegtreeOperator<long>.Identity => long.MinValue; long ISegtreeOperator<long>.Operate(long x, long y) => Math.Max(x, y); } } |
遅延評価セグメント木
セグメント木は 配列の1要素を更新する、区間の集計結果（最小値や総和など）を取得するときに威力を発揮しました。では配列の1要素の更新ではなく区間の要素をまとめて更新する処理が必要なときはどうすればよいでしょうか？ このときに使えるのが遅延評価セグメント木です。
x を b x + c で更新する
数列の半開区間 [l,r) 内の各要素の値を b 倍して c を足す
数列の半開区間 [l,r) 内の各要素の総和を 998244353 で割った余りを答える
このようなクエリに高速で答える問題です。
b 倍して c を足すという操作を区間に対しておこなう場合、その総和は（b * 区間の総和 + c * 区間の長さ）となります。なので総和だけでなく区間の長さも持つ必要があります。区間の総和を取得する問題において、区間の長さを Node に持たせるのは、セグメント木の典型らしいです。
そこで 以下のような構造体を定義します（クラスだと処理に時間がかかって TLE してしまう）。
|
1 2 3 4 5 6 7 8 9 10 11 |
struct Node { public Node(long v, int length) { Sum = v % mod; Length = length; } public long Sum = 0; public int Length = 0; int mod = 998244353; } |
また各要素の値を b 倍して c を足すという操作が必要なので配列の値に作用させる b と c を構造体にします。
|
1 2 3 4 5 6 7 8 9 10 11 |
struct F { public F(long b, long c) { B = b % mod; C = c % mod; } public long B = 0; public long C = 0; int mod = 998244353; } |
遅延セグメント木では通常のセグメント木に加えて、作用の単位元、作用関数、作用の合成関数が必要です。
作用関数は上に述べたように（b * 区間の総和 + c * 区間の長さ）です。また x に b と c を作用させると y = b * x + c になりますが、ここへ更に b’ と c’ を作用させると y’ = b’ * y + c’ = y’ = b’ * (b * x + c) + c’ = (b’ * b) * x + (b’ * c + c’) となるので作用の合成関数は下記のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 |
struct SegtreeOperator : ILazySegtreeOperator<Node, F> { Node ISegtreeOperator<Node>.Identity => new Node(0, 0); // 単位元 Node ISegtreeOperator<Node>.Operate(Node x, Node y) => new Node(x.Sum + y.Sum, x.Length + y.Length); // 二項演算 F ILazySegtreeOperator<Node, F>.FIdentity => new F(1, 0); // 作用の単位元 Node ILazySegtreeOperator<Node, F>.Mapping(F f, Node x) => new Node(f.B * x.Sum + f.C * x.Length, x.Length); // 作用関数 F ILazySegtreeOperator<Node, F>.Composition(F nf, F cf) => new F(nf.B * cf.B, nf.B * cf.C + nf.C); // 作用の合成関数 } |
あとはコードを書くだけです。
|
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 30 31 32 33 34 35 36 37 38 39 |
using AtCoder; class Program { static void Main() { SourceExpander.Expander.Expand(); int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); Node[] nodes = new Node[N]; for (int i = 0; i < N; i++) nodes[i] = new Node(A[i], 1); AtCoder.LazySegtree<Node, F, SegtreeOperator> lazySegtree = new AtCoder.LazySegtree<Node, F, SegtreeOperator>(nodes); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; int left = vs[1]; int right = vs[2]; if (t == 0) { int b = vs[3]; int c = vs[4]; lazySegtree.Apply(left, right, new F(b, c)); } if (t == 1) Console.WriteLine(lazySegtree.Prod(left, right).Sum); } } } |
転倒数
数列 A の転倒数とは i < j, A[i] ≧ A[j] を満たす整数の組の数です。数列を昇順にソートする時、「正しい順序になっていないペアの数」と考えることもできます。転倒数は「自分より右にある、自分より小さな数の個数」を全要素求めて足し合わせることで求めることができます。
クエリによって 0 と 1 が反転するので区間内部の 0 と 1 の個数を記憶しておく必要があります。また数列内には 0 と 1 しかないので 0 と 1 の個数から転倒数を求めることができます。ふたつの連続する区間の 0 と 1 の数と転倒数がわかっているのであれば、それらをつなげた区間の転倒数は（前の区間の転倒数 + 後ろの区間の転倒数 + 前の区間の 1 の個数 * 後ろの区間の 0 の個数）となります。
そこで以下のような構造体を定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
struct Node { public Node(long zero, long one, long tentou) { Zero = zero; One = one; Tentou = tentou; } public long Zero = 0; // 区間内部の 0 と 1 の個数 public long One = 0; public long Tentou = 0; // 区間内部の転倒数 } |
もしある区間の 0 と 1 を反転させたらどうなるでしょうか？ すぐに気がつくこととして、Node.Zeroの値とNode.Oneの値が入れ替わります。
では転倒数はどうなるでしょうか？ 0 と 1 のペアの個数は反転しても変化せずに Node.Zero * Node.One のままです。ここから元の転倒数を引けば反転後の転倒数がわかります。
単位元は区間の 0 と 1 の個数も転倒数も 0 とします。ここでいう「作用」とはある区間における 0 と 1 の反転です。作用の単位元は「反転はしない」、すなわち false です。作用関数は上で述べたとおり、Node.Zeroの値とNode.Oneの値が入れ替え、新しい転倒数を Node.Zero * Node.One – Node.Tentou とするオブジェクトを返します。作用の合成関数は新しい作用がtrueなら古い作用の true と false を反転させます。
したがって以下のようになります。
|
1 2 3 4 5 6 7 8 9 10 |
struct SegtreeOperator : ILazySegtreeOperator<Node, bool> { Node ISegtreeOperator<Node>.Identity => new Node(0, 0, 0);// 単位元 bool ILazySegtreeOperator<Node, bool>.FIdentity => false; // 作用の単位元 bool ILazySegtreeOperator<Node, bool>.Composition(bool nf, bool cf) => nf ? !cf : cf; // 作用の合成関数 Node ILazySegtreeOperator<Node, bool>.Mapping(bool f, Node x) => f ? new Node(x.One, x.Zero, x.One * x.Zero - x.Tentou) : x; // 作用関数 Node ISegtreeOperator<Node>.Operate(Node x, Node y) => new Node(x.Zero + y.Zero, x.One + y.One, x.Tentou + y.Tentou + x.One * y.Zero); // 二項演算 } |
|
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 30 31 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); LazySegtree<Node, bool, SegtreeOperator> lazySegtree = new LazySegtree<Node, bool, SegtreeOperator>(N); for (int i = 0; i < N; i++) lazySegtree[i] = A[i] == 1 ? new Node(0, 1, 0) : new Node(1, 0, 0); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int t = vs[0]; int left = vs[1] - 1; // 1-indexed -> 0-index int right = vs[2]; if (t == 1) lazySegtree.Apply(left, right, true); if (t == 2) Console.WriteLine(lazySegtree.Prod(left, right).Tentou); } } } |
