AtCoder NoviStepsを埋めてみる(35) セグメント木（segment tree）1D

AtCoder NoviStepsを埋めてみる(34) セグメント木（segment tree）の続きです。今回もセグメント木（segment tree）です。前回同様 ac-library-csharp の Segtree<T> クラスを使います。

参考： ac-library-csharpを使ってみる(セグメント木編)

D – Flat Subsequence

問題の概要

長さ N の数列 A と整数 K が与えられる。
以下の条件を満たす数列 B の長さとして考えられる最大値を出力せよ。

条件
B は A の (連続とは限らない) 部分列である。
どの B の隣り合う要素の差の絶対値も K 以下である。

動的計画法で考えます。

dp[v]: 最後の項の値が v となる場合についての最長の長さ
dp[v] = Math.Max(dp[v], dp.Max(v – K, v + K) + 1);

dp 自体を配列ではなくセグ木にしてしまえば処理を高速化できます。

RangeMaxQuery クラスは A58 – RMQ (Range Maximum Queries) を参照してください。

// RangeMaxQuery クラスは省略

class Program
{
    static void Main()
    {
        int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int K) = (nk[0], nk[1]);

        int[] A = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = int.Parse(Console.ReadLine());

        int max_col = 300010;
        RangeMaxQuery dp = new RangeMaxQuery(new long[max_col]);

        foreach (int v in A)
        {
            int min_idx = Math.Max(v - K, 0);
            int max_idx = Math.Min(v + K, max_col - 1);
            long next_v = dp.Max(min_idx, max_idx) + 1;
            dp[v] = Math.Max(dp[v], next_v);
        }

        Console.WriteLine(dp.Max(0, max_col - 1));
    }
}

// RangeMaxQuery クラスは省略

class Program

{

static void Main()

{

int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int K) = (nk[0], nk[1]);

int[] A = new int[N];

for (int i = 0; i < N; i++)

A[i] = int.Parse(Console.ReadLine());

int max_col = 300010;

RangeMaxQuery dp = new RangeMaxQuery(new long[max_col]);

foreach (int v in A)

{

int min_idx = Math.Max(v - K, 0);

int max_idx = Math.Min(v + K, max_col - 1);

long next_v = dp.Max(min_idx, max_idx) + 1;

dp[v] = Math.Max(dp[v], next_v);

}

Console.WriteLine(dp.Max(0, max_col - 1));

}

B58 – Jumping

問題の概要

N 個の足場が横一列に番号順に並んでいる。
足場 1 がスタート地点、足場 N がゴール地点であり、足場 i はスタート地点から X[i] の位置にある。

1 回で L 以上 R 以下の距離を右方向にのみジャンプできるとき、スタートからゴールまで移動するために必要なジャンプ回数の最小値を求めよ。
ただし、与えられる入力ではスタートからゴールまで到達できることが保証されている。

動的計画法で考えます。

二分探索で足場 i へジャンプできる足場の添字の最大値と最小値を求めておきます。

dp[i]: 足場 i へたどりつくためのジャンプの回数の最小値
idx_min：足場 i へジャンプできる足場の添字の最小値
idx_max：足場 i へジャンプできる足場の添字の最大値
dp[i] = dp.Min(idx_min, idx_max) + 1;
（dpを ∞ で初期化するが、1 を加算する処理があるのでオーバーフローに注意）

using AtCoder;

class RangeMinQuery
{
    struct OP : ISegtreeOperator<long>
    {
        long ISegtreeOperator<long>.Identity => long.MaxValue;
        long ISegtreeOperator<long>.Operate(long x, long y) => Math.Min(x, y);
    }

    Segtree<long, OP> seg;
    public RangeMinQuery(long[] arr) => seg = new Segtree<long, OP>(arr);

    public long this[int idx]
    {
        get { return seg[idx]; }
        set { seg[idx] = value; }
    }

    // 閉区間 [l, r] の最小値を求める
    public long Min(int l, int r) => seg.Prod(l, r + 1);
}

class Program
{
    static void Main()
    {
        int[] nlr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int L, int R) = (nlr[0], nlr[1], nlr[2]);

        int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        List<(int idx, int min_idx, int max_idx)> tps = new List<(int, int, int)>();
        for (int i = 1; i < N; i++)
        {
            int cur = X[i];
            int ok = N;
            int ng = -1;
            int min_idx = StlFunction.BinarySearch(ok, ng, mid => cur - R <= X[mid]);
            int max_idx = StlFunction.BinarySearch(ok, ng, mid => cur - L < X[mid]) - 1;
            if (max_idx < min_idx)
            {
                max_idx = -1; // 該当する区間は存在しない
                min_idx = -1;
            }
            tps.Add((i, min_idx, max_idx));
        }

        RangeMinQuery dp = new RangeMinQuery(new long[N]);
        for (int i = 1; i < N; i++)
            dp[i] = long.MaxValue / 2; // ∞で初期化（オーバーフローに注意）
        dp[0] = 0;

        foreach (var tp in tps)
        {
            if (tp.min_idx != -1)
                dp[tp.idx] = dp.Min(tp.min_idx, tp.max_idx) + 1;
        }
        Console.WriteLine(dp[N - 1]);
    }
}

using AtCoder;

class RangeMinQuery

{

struct OP : ISegtreeOperator<long>

{

long ISegtreeOperator<long>.Identity => long.MaxValue;

long ISegtreeOperator<long>.Operate(long x, long y) => Math.Min(x, y);

}

Segtree<long, OP> seg;

public RangeMinQuery(long[] arr) => seg = new Segtree<long, OP>(arr);

public long this[int idx]

{

get { return seg[idx]; }

set { seg[idx] = value; }

}

// 閉区間 [l, r] の最小値を求める

public long Min(int l, int r) => seg.Prod(l, r + 1);

}

class Program

{

static void Main()

{

int[] nlr = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int L, int R) = (nlr[0], nlr[1], nlr[2]);

int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

List<(int idx, int min_idx, int max_idx)> tps = new List<(int, int, int)>();

for (int i = 1; i < N; i++)

{

int cur = X[i];

int ok = N;

int ng = -1;

int min_idx = StlFunction.BinarySearch(ok, ng, mid => cur - R <= X[mid]);

int max_idx = StlFunction.BinarySearch(ok, ng, mid => cur - L < X[mid]) - 1;

if (max_idx < min_idx)

{

max_idx = -1; // 該当する区間は存在しない

min_idx = -1;

}

tps.Add((i, min_idx, max_idx));

}

RangeMinQuery dp = new RangeMinQuery(new long[N]);

for (int i = 1; i < N; i++)

dp[i] = long.MaxValue / 2; // ∞で初期化（オーバーフローに注意）

dp[0] = 0;

foreach (var tp in tps)

{

if (tp.min_idx != -1)

dp[tp.idx] = dp.Min(tp.min_idx, tp.max_idx) + 1;

}

Console.WriteLine(dp[N - 1]);

}

037 – Don’t Leave the Spice（★5）

香辛料を使う料理が N 種類ある。

料理 i (1 ≦ i ≦ N) の価値は V[i] で、作るときに香辛料を消費する。消費する香辛料の量は L[i] 以上 R[i] 以下の範囲で調節できる。

N 種類の料理から何種類かを選んでひとつずつ作ることで、香辛料の消費量の合計をちょうど W にすることが可能かどうか判定せよ。可能である場合は作る料理の価値の合計としてあり得る最大の値を出力せよ。

動的計画法で考えます。

dp[col]：香辛料の消費量の合計が col のときの料理の価値の合計の最大値
dp[col] = dp.Max(col – r, col – l) + v;
※ dp[col – j] にアクセスするときに配列外アクセスにならないように注意
※ [col – r, col – l] がすべて負数のときは更新できない。
※ col が大きなものから更新することで同じオブジェクトを使い回すことができる。

// RangeMaxQuery クラスは省略

class Program
{
    static void Main()
    {
        int[] wn = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int W, int N) = (wn[0], wn[1]);

        RangeMaxQuery dp = new RangeMaxQuery(new long[W + 1]);
        for (int i = 1; i <= W; i++)
            dp[i] = long.MinValue;
        dp[0] = 0;

        for (int i = 0; i < N; i++)
        {
            int[] lrv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            (int l, int r, int v) = (lrv[0], lrv[1], lrv[2]);
            for (int col = W; col >= 0; col--)
            {
                int max_idx = col - l;
                int min_idx = col - r;

                if (max_idx < 0)
                    continue;
                if (min_idx < 0)
                    min_idx = 0;

                long max_v = dp.Max(min_idx, max_idx);
                if (max_v >= 0)
                    dp[col] = Math.Max(dp[col], max_v + v);
            }
        }
        Console.WriteLine(dp[W] >= 0 ? dp[W] : -1);
    }
}

// RangeMaxQuery クラスは省略

class Program

{

static void Main()

{

int[] wn = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int W, int N) = (wn[0], wn[1]);

RangeMaxQuery dp = new RangeMaxQuery(new long[W + 1]);

for (int i = 1; i <= W; i++)

dp[i] = long.MinValue;

dp[0] = 0;

for (int i = 0; i < N; i++)

{

int[] lrv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int l, int r, int v) = (lrv[0], lrv[1], lrv[2]);

for (int col = W; col >= 0; col--)

{

int max_idx = col - l;

int min_idx = col - r;

if (max_idx < 0)

continue;

if (min_idx < 0)

min_idx = 0;

long max_v = dp.Max(min_idx, max_idx);

if (max_v >= 0)

dp[col] = Math.Max(dp[col], max_v + v);

}

Console.WriteLine(dp[W] >= 0 ? dp[W] : -1);

}

Q – Flowers

問題の概要

N 本の花が横一列に並んでいる。
i 番目の花の高さは H[i] で、美しさは A[i] である。ただし H はすべて異なる値である。

何本かの花を抜き去り、高さが単調増加になるようにしたい。
残りの花の美しさの総和の最大値を求めよ。

動的計画法で考えます。

dp[h]: 最後に選んだ花の高さが h となる場合の選ばれた花の美しさの総和の最大値
dp[h] = dp.Max(0, h – 1) + A[i];

// RangeMaxQuery クラスは省略

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        int[] H = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        RangeMaxQuery dp = new RangeMaxQuery(new long[N + 1]);
        for (int i = 0; i < N; i++)
        {
            int h = H[i];
            int v = A[i];
            dp[h] = dp.Max(0, h - 1) + A[i];
        }

        long ans = 0;
        for (int h = 0; h <= N; h++)
            ans = Math.Max(ans, dp[h]);

        Console.WriteLine(ans);
    }
}

// RangeMaxQuery クラスは省略

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] H = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

RangeMaxQuery dp = new RangeMaxQuery(new long[N + 1]);

for (int i = 0; i < N; i++)

{

int h = H[i];

int v = A[i];

dp[h] = dp.Max(0, h - 1) + A[i];

}

long ans = 0;

for (int h = 0; h <= N; h++)

ans = Math.Max(ans, dp[h]);

Console.WriteLine(ans);

}

F – Second Largest Query

問題の概要

長さ N の数列 A が与えられる。
Q 個のクエリが与えられるので処理せよ。

クエリ 1 : A[p] の値を x に変更する。
クエリ 2 : A[l] ,A[l + 1], …, A[r] において二番目に大きい値の個数を出力する。

構造体を使って区間 [l, r] における最大値、最大値の個数、二番目に大きい値、二番目に大きい値の個数の 4 要素を管理すればよいのですが、処理を工夫しないと TLE してしまいます。

using AtCoder;

class RangeMaxQuery2
{
    public struct Data
    {
        public Data()
        {
        }

        public Data(int first_v)
        {
            Values[0] = first_v;
            Counts[0] = 1;
        }

        public Data(int first_v, int first_cnt, int second_v, int second_cnt)
        {
            Values[0] = first_v;
            Counts[0] = first_cnt;
            Values[1] = second_v;
            Counts[1] = second_cnt;
        }

        public int[] Values = new int[2];
        public int[] Counts = new int[2];
    }

    struct OP : ISegtreeOperator<Data>
    {
        Data ISegtreeOperator<Data>.Identity => new Data();

        // 2つを統合するときには、上位 2 つの値と個数を調べる
        // 必要な処理だけに限定しないと時間がかかりすぎて TLE する。
        Data ISegtreeOperator<Data>.Operate(Data x, Data y)
        {
            int[] values = new int[2];
            int[] counts = new int[2];
            if (x.Values[0] > y.Values[0])
            {
                values[0] = x.Values[0];
                counts[0] = x.Counts[0];
                if (x.Values[1] == y.Values[0])
                {
                    values[1] = x.Values[1];
                    counts[1] = x.Counts[1] + y.Counts[0];
                }
                else
                {
                    values[1] = x.Values[1] > y.Values[0] ? x.Values[1] : y.Values[0];
                    counts[1] = x.Values[1] > y.Values[0] ? x.Counts[1] : y.Counts[0];
                }
            }
            else if (x.Values[0] < y.Values[0])
            {
                values[0] = y.Values[0];
                counts[0] = y.Counts[0];

                if (x.Values[0] == y.Values[1])
                {
                    values[1] = x.Values[0];
                    counts[1] = x.Counts[0] + y.Counts[1];
                }
                else
                {
                    values[1] = x.Values[0] > y.Values[1] ? x.Values[0] : y.Values[1];
                    counts[1] = x.Values[0] > y.Values[1] ? x.Counts[0] : y.Counts[1];
                }
            }
            else
            {
                values[0] = x.Values[0];
                counts[0] = x.Counts[0] + y.Counts[0];

                if (x.Values[1] == y.Values[1])
                {
                    values[1] = x.Values[1];
                    counts[1] = x.Counts[1] + y.Counts[1];
                }
                else
                {
                    values[1] = x.Values[1] > y.Values[1] ? x.Values[1] : y.Values[1];
                    counts[1] = x.Values[1] > y.Values[1] ? x.Counts[1] : y.Counts[1];
                }
            }
            return new Data(values[0], counts[0], values[1], counts[1]);
        }
    }

    Segtree<Data, OP> seg;

    public RangeMaxQuery2(int[] arr)
    {
        Data[] datas = arr.Select(_ => new Data(_)).ToArray();
        seg = new Segtree<Data, OP>(datas);
    }

    public int this[int idx]
    {
        set { seg[idx] = new Data(value); }
    }

    // 閉区間 [l, r] の二番目に大きい値の個数を求める
    public int Solve(int l, int r)
    { 
        Data data = seg.Prod(l, r + 1);
        return data.Counts[1];
    }
}

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int Q) = (nq[0], nq[1]);

        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        RangeMaxQuery2 rmq = new RangeMaxQuery2(A);
        List<int> ans = new List<int>();

        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            if (t == 1)
            {
                int p = query[1] - 1;
                int x = query[2];
                rmq[p] = x;
            }
            if (t == 2)
            {
                int l = query[1] - 1;
                int r = query[2] - 1;
                int res = rmq.Solve(l, r);
                ans.Add(res);
            }
        }
        foreach (int v in ans)
            Console.WriteLine(v);
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

using AtCoder;

class RangeMaxQuery2

{

public struct Data

{

public Data()

{

}

public Data(int first_v)

{

Values[0] = first_v;

Counts[0] = 1;

}

public Data(int first_v, int first_cnt, int second_v, int second_cnt)

{

Values[0] = first_v;

Counts[0] = first_cnt;

Values[1] = second_v;

Counts[1] = second_cnt;

}

public int[] Values = new int[2];

public int[] Counts = new int[2];

}

struct OP : ISegtreeOperator<Data>

{

Data ISegtreeOperator<Data>.Identity => new Data();

// 2つを統合するときには、上位 2 つの値と個数を調べる

// 必要な処理だけに限定しないと時間がかかりすぎて TLE する。

Data ISegtreeOperator<Data>.Operate(Data x, Data y)

{

int[] values = new int[2];

int[] counts = new int[2];

if (x.Values[0] > y.Values[0])

{

values[0] = x.Values[0];

counts[0] = x.Counts[0];

if (x.Values[1] == y.Values[0])

{

values[1] = x.Values[1];

counts[1] = x.Counts[1] + y.Counts[0];

}

else

{

values[1] = x.Values[1] > y.Values[0] ? x.Values[1] : y.Values[0];

counts[1] = x.Values[1] > y.Values[0] ? x.Counts[1] : y.Counts[0];

}

else if (x.Values[0] < y.Values[0])

{

values[0] = y.Values[0];

counts[0] = y.Counts[0];

if (x.Values[0] == y.Values[1])

{

values[1] = x.Values[0];

counts[1] = x.Counts[0] + y.Counts[1];

}

else

{

values[1] = x.Values[0] > y.Values[1] ? x.Values[0] : y.Values[1];

counts[1] = x.Values[0] > y.Values[1] ? x.Counts[0] : y.Counts[1];

}

else

{

values[0] = x.Values[0];

counts[0] = x.Counts[0] + y.Counts[0];

if (x.Values[1] == y.Values[1])

{

values[1] = x.Values[1];

counts[1] = x.Counts[1] + y.Counts[1];

}

else

{

values[1] = x.Values[1] > y.Values[1] ? x.Values[1] : y.Values[1];

counts[1] = x.Values[1] > y.Values[1] ? x.Counts[1] : y.Counts[1];

}

return new Data(values[0], counts[0], values[1], counts[1]);

}

Segtree<Data, OP> seg;

public RangeMaxQuery2(int[] arr)

{

Data[] datas = arr.Select(_ => new Data(_)).ToArray();

seg = new Segtree<Data, OP>(datas);

}

public int this[int idx]

{

set { seg[idx] = new Data(value); }

}

// 閉区間 [l, r] の二番目に大きい値の個数を求める

public int Solve(int l, int r)

{

Data data = seg.Prod(l, r + 1);

return data.Counts[1];

}

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int Q) = (nq[0], nq[1]);

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

RangeMaxQuery2 rmq = new RangeMaxQuery2(A);

List<int> ans = new List<int>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

int p = query[1] - 1;

int x = query[2];

rmq[p] = x;

}

if (t == 2)

{

int l = query[1] - 1;

int r = query[2] - 1;

int res = rmq.Solve(l, r);

ans.Add(res);

}

foreach (int v in ans)

Console.WriteLine(v);

}

F – Parenthesis Checking

問題の概要

Q 個のクエリが与えられるので処理せよ。
クエリ 1：S の l 文字目と r 文字目を入れ替える。
クエリ 2：S の l 文字目から r 文字目までの連続部分文字列が正しい括弧列であるか判定する。

以下を正しい括弧列と定義する。
(1) 空文字列
(2) ある正しい括弧列 A が存在して、(, A, ) をこの順に連結した文字列
(3) ある空でない正しい括弧列 A, B が存在して、A, B をこの順に連結した文字列

括弧列の特徴は以下のとおりです。

① 文字列 S に含まれる(と)の個数は等しい
② 任意の 1 ≦ k ≦ |S| に対して、S の k 文字目までに含まれる ‘(‘ の個数 ≧ S の文字目までに含まれる ‘)’ の個数が成り立つ

A[i] を S[i] == ‘(‘ なら 1 、S[i] == ‘)’ なら -1 と定義します。そして A の i までの累積和を sums[i + 1] とします。まず、① の性質より sums[l] == sums[r + 1] となっていなければなりません。また ② の性質より min(sums[l + 1], sums[l + 2], …, sums[r + 1]) ≧ sums[l] となっていなければなりません。

クエリに対応するために、区間加算の処理と区間最小値を取得できる遅延評価型セグメント木を構築します。

クエリ 1 への対応ですが、S の l 文字目と r 文字目を入れ替えたときに同じ文字を入れ替えるのであれば何もする必要はありません。異なる文字を入れ替えたときは sums の閉区間 [l + 1, r + 1] が 2 増えるか減るかのどちらかです。クエリ 2 に対しては sums[l] == sums[r + 1] かつ sums.Min(l + 1, r + 1) ≧ sums[l] であるかどうかを調べればよいです。

using AtCoder;

// 区間加算の処理と区間最小値の取得ができる遅延評価型セグメント木
class RangeAddMinQuery
{
    struct OP : ILazySegtreeOperator<long, long>
    {
        long ISegtreeOperator<long>.Identity => long.MaxValue / 2;
        long ILazySegtreeOperator<long, long>.FIdentity => 0;
        long ILazySegtreeOperator<long, long>.Composition(long nf, long cf) => nf + cf;
        long ILazySegtreeOperator<long, long>.Mapping(long f, long x) => x + f;
        long ISegtreeOperator<long>.Operate(long x, long y) => Math.Min(x, y);
    }

    LazySegtree<long, long, OP> seg;
    public RangeAddMinQuery(long[] arr) => seg = new LazySegtree<long, long, OP>(arr);

    public long this[int idx]
    {
        get { return seg[idx]; }
        set { seg[idx] = value; }
    }

    // 閉区間 [l, r] の Min を求める
    public long Min(int l, int r) => seg.Prod(l, r + 1);

    // 閉区間 [l, r] に v を加算する
    public void Add(int l, int r, long v) => seg.Apply(l, r, v);
}

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int Q) = (nq[0], nq[1]);

        char[] S = Console.ReadLine().ToArray();

        RangeAddMinQuery sums = new RangeAddMinQuery(new long[N + 1]);

        for (int i = 0; i < N; i++)
            sums[i + 1] = sums[i] + (S[i] == '(' ? 1 : -1);

        List<string> ans = new List<string>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            (int t, int l, int r) = (query[0], query[1] - 1, query[2] - 1);
            if (t == 1)
            {
                (S[l], S[r]) = (S[r], S[l]);
                if (S[l] != S[r])
                {
                    if (S[l] == '(')
                        sums.Add(l + 1, r + 1, 2);
                    if (S[l] == ')')
                        sums.Add(l + 1, r + 1, -2);
                }
            }
            if (t == 2)
                ans.Add(sums[l] == sums[r + 1] && sums.Min(l + 1, r + 1) >= sums[l] ? "Yes" : "No");
        }

        foreach (string str in ans)
            Console.WriteLine(str);
    }
}

using AtCoder;

// 区間加算の処理と区間最小値の取得ができる遅延評価型セグメント木

class RangeAddMinQuery

{

struct OP : ILazySegtreeOperator<long, long>

{

long ISegtreeOperator<long>.Identity => long.MaxValue / 2;

long ILazySegtreeOperator<long, long>.FIdentity => 0;

long ILazySegtreeOperator<long, long>.Composition(long nf, long cf) => nf + cf;

long ILazySegtreeOperator<long, long>.Mapping(long f, long x) => x + f;

long ISegtreeOperator<long>.Operate(long x, long y) => Math.Min(x, y);

}

LazySegtree<long, long, OP> seg;

public RangeAddMinQuery(long[] arr) => seg = new LazySegtree<long, long, OP>(arr);

public long this[int idx]

{

get { return seg[idx]; }

set { seg[idx] = value; }

}

// 閉区間 [l, r] の Min を求める

public long Min(int l, int r) => seg.Prod(l, r + 1);

// 閉区間 [l, r] に v を加算する

public void Add(int l, int r, long v) => seg.Apply(l, r, v);

}

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int Q) = (nq[0], nq[1]);

char[] S = Console.ReadLine().ToArray();

RangeAddMinQuery sums = new RangeAddMinQuery(new long[N + 1]);

for (int i = 0; i < N; i++)

sums[i + 1] = sums[i] + (S[i] == '(' ? 1 : -1);

List<string> ans = new List<string>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int t, int l, int r) = (query[0], query[1] - 1, query[2] - 1);

if (t == 1)

{

(S[l], S[r]) = (S[r], S[l]);

if (S[l] != S[r])

{

if (S[l] == '(')

sums.Add(l + 1, r + 1, 2);

if (S[l] == ')')

sums.Add(l + 1, r + 1, -2);

}

if (t == 2)

ans.Add(sums[l] == sums[r + 1] && sums.Min(l + 1, r + 1) >= sums[l] ? "Yes" : "No");

}

foreach (string str in ans)

Console.WriteLine(str);

}

B59 – Number of Inversions

問題の概要

長さ N の数列 A が与えられる。
1 ≦ i < j ≦ N かつ A[i] > A[j] を満たす整数の組 (i, j) の個数を求めよ。

値 v が A のなかに何個あるかを管理する配列 counts を定義します。

A[i] を順番に読み込み、counts[A[i]] をデクリメントしたあと、counts.Sum(0, A[i] – 1) を求めます。これが i における A[i] > A[j] を満たす整数の組 (i, j) の個数です。0 ≦ i ≦ N – 1 についてすべて足したものが解となります。

// RangeSumQuery クラスは省略

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        RangeSumQuery counts = new RangeSumQuery(new long[N + 1]);
        for (int i = 1; i <= N; i++)
            counts[i] = 1;

        long ans = 0;
        foreach (var v in A)
        {
            counts[v]--;
            ans += counts.Sum(0, v - 1);
        }
        Console.WriteLine(ans);
    }
}

// RangeSumQuery クラスは省略

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

RangeSumQuery counts = new RangeSumQuery(new long[N + 1]);

for (int i = 1; i <= N; i++)

counts[i] = 1;

long ans = 0;

foreach (var v in A)

{

counts[v]--;

ans += counts.Sum(0, v - 1);

}

Console.WriteLine(ans);

}

F – Double Sum

問題の概要

整数列 A が与えられる。次の式を計算せよ。

すべての i に対して i < j かつ A[i] < A[j] を満たす j の個数と A[j] の総和がわかるなら、与式の答えは (A[j] の総和 – j の個数 × A[i]) の総和です。では j の個数と A[j] の総和はどうやって求めればよいでしょうか？

(i, A[i]) をペアにしたものを A の値で降順ソートします。そして順番に (i, A[i]) を取り出し、counts[i] = 1, sums[i] = A[i] とします。counts において i よりも右側の要素の総和を求めれば i < j かつ A[i] < A[j] を満たす j の個数がわかります。同様に sums において i よりも右側の要素の総和を求めれば i < j かつ A[i] < A[j] を満たす A[j] の総和がわかります。これで (A[j] の総和 – j の個数 × A[i]) がわかるのでその総和を求めれば問題の解が得られます。

// RangeSumQuery クラスは省略

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        List<(int idx, int v)> pairs = new List<(int idx, int v)>();
        for (int i = 0; i < N; i++)
            pairs.Add((i, A[i]));

        pairs = pairs.OrderByDescending(_ => _.v).ToList();

        RangeSumQuery sums = new RangeSumQuery(new long[N]);
        RangeSumQuery counts = new RangeSumQuery(new long[N]);

        long ans = 0;
        foreach (var pair in pairs)
        {
            counts[pair.idx] = 1;
            sums[pair.idx] = pair.v;
            ans += sums.Sum(pair.idx + 1, N - 1) - counts.Sum(pair.idx + 1, N - 1) * pair.v;
        }
        Console.WriteLine(ans);
    }
}

// RangeSumQuery クラスは省略

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

List<(int idx, int v)> pairs = new List<(int idx, int v)>();

for (int i = 0; i < N; i++)

pairs.Add((i, A[i]));

pairs = pairs.OrderByDescending(_ => _.v).ToList();

RangeSumQuery sums = new RangeSumQuery(new long[N]);

RangeSumQuery counts = new RangeSumQuery(new long[N]);

long ans = 0;

foreach (var pair in pairs)

{

counts[pair.idx] = 1;

sums[pair.idx] = pair.v;

ans += sums.Sum(pair.idx + 1, N - 1) - counts.Sum(pair.idx + 1, N - 1) * pair.v;

}

Console.WriteLine(ans);

}

J – Segment Tree

問題の概要

長さ N の整数列 A が与えられる。Q 個のクエリを処理せよ。

クエリ 1：A[x] を v で更新する。
クエリ 2：A[j] (l ≦ j ≦ r) の最大値を求める。
クエリ 3：x ≦ j ≦ N, v ≦ A[j] を満たす最小の j を求める。

セグメント木であればクエリ 1 と 2 は簡単にできそうです。実はクエリ 3 も二分探索法を用いれば同じセグメント木の上でできます。

// RangeMaxQuery クラスは省略

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int Q) = (nq[0], nq[1]);

        long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

        RangeMaxQuery rmq = new RangeMaxQuery(A);

        List<long> ans = new List<long>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            if (t == 1)
            {
                (int x, int v) = (query[1] - 1, query[2]);
                rmq[x] = v;
            }
            if (t == 2)
            {
                (int l, int r) = (query[1] - 1, query[2] - 1);
                long max = rmq.Max(l, r);
                ans.Add(max);
            }
            if (t == 3)
            {
                (int x, int v) = (query[1] - 1, query[2]);
                int ok = N;
                int ng = x - 1;
                int idx = StlFunction.BinarySearch(ok, ng, mid => rmq.Max(x, mid) >= v);
                ans.Add(idx + 1);
            }
        }

        foreach (long v in ans)
            Console.WriteLine(v);
    }
}

// RangeMaxQuery クラスは省略

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int Q) = (nq[0], nq[1]);

long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray();

RangeMaxQuery rmq = new RangeMaxQuery(A);

List<long> ans = new List<long>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

(int x, int v) = (query[1] - 1, query[2]);

rmq[x] = v;

}

if (t == 2)

{

(int l, int r) = (query[1] - 1, query[2] - 1);

long max = rmq.Max(l, r);

ans.Add(max);

}

if (t == 3)

{

(int x, int v) = (query[1] - 1, query[2]);

int ok = N;

int ng = x - 1;

int idx = StlFunction.BinarySearch(ok, ng, mid => rmq.Max(x, mid) >= v);

ans.Add(idx + 1);

}

foreach (long v in ans)

Console.WriteLine(v);

}

F – Insert

問題の概要

配列 P が与えられる。
空の配列 A に対して i = 1, 2, …, N の順に数 i を A の前から P[i] 番目の位置になるように挿入していく場合、すべての操作を終えた後の A を出力せよ。

操作を逆順に考えるとうまくいきます。

A’ = (1, 2, …, N) に対し、i = N, N – 1, …, 1 の順に以下の問題を考えます。

A’ の P[i] 番目の要素を削除し、残りの要素は順序を保って詰める。
各操作で削除される数を B[i] とする。これを求めよ。

各操作で削除される数の求め方ですが、長さ N の配列 T を定義し、i が A’ のなかに含まれていたら T[i] = 1、そうでなければ T[i] = 0 とします。最初はすべての要素が 1 です。

A’ の P[i] 番目の要素を削除するときは (T[0] + T[1] + … + T[j]) = P[i] を満たす最小の j を二分探索法で探し、T[j] を 0 に更新して B[i] = j とします。

B を反転して A[B[i]] = i + 1 とすれば操作後の A を求めることができます。

// RangeSumQuery クラスは省略

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        Array.Reverse(P);

        List<int> B = new List<int>();

        RangeSumQuery rsq = new RangeSumQuery(new long[N]);
        for (int i = 0; i < N; i++)
            rsq[i] = 1;

        foreach (var v in P)
        {
            int ok = N;
            int ng = -1;
            int idx = StlFunction.BinarySearch(ok, ng, mid => rsq.Sum(0, mid) >= v);
            rsq[idx] = 0;
            B.Add(idx);
        }
        B.Reverse();

        int[] A = new int[N];
        for (int i = 0; i < N; i++)
            A[B[i]] = i + 1;

        Console.WriteLine(string.Join(" ", A));
    }
}

// RangeSumQuery クラスは省略

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] P = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

Array.Reverse(P);

List<int> B = new List<int>();

RangeSumQuery rsq = new RangeSumQuery(new long[N]);

for (int i = 0; i < N; i++)

rsq[i] = 1;

foreach (var v in P)

{

int ok = N;

int ng = -1;

int idx = StlFunction.BinarySearch(ok, ng, mid => rsq.Sum(0, mid) >= v);

rsq[idx] = 0;

B.Add(idx);

}

B.Reverse();

int[] A = new int[N];

for (int i = 0; i < N; i++)

A[B[i]] = i + 1;

Console.WriteLine(string.Join(" ", A));

}

E – A > B substring

問題の概要

A, B, C の 3 種類の文字からなる長さ N の文字列 S が与えられる。
S の空でない連続する部分文字列は N × (N + 1) / 2 個存在するが、そのなかに A が B よりも多く含まれるものはいくつあるか求めよ。

S の先頭 i 文字の中にある A の個数を A[i]、B の個数を B[i] とします。

S の i 文字目から j 文字目までを取って得られる部分文字列が条件を満たすことは、A[j] – A[i – 1] > B[j] – B[i – 1] （ただし i <= j）と言い換えることができます。これは式変形をすることで A[j] - B[j] > A[i - 1] - B[i - 1] となります。 C[i] = A[i] - B[i] とおくと、C[i] < C[j]（ただし i < j）を満たす (i, j) の個数が求める解となります。B59 – Number of Inversions とは逆の処理（C[i] > C[j] ではなく C[i] < C[j] を数える）をすればよいのですが、C に値の重複がある場合があること、C[i] が負数の場合があるので全体に同じ値を加算して全要素を非負に変換してから処理をしなければならない点に注意が必要です。

// RangeSumQuery クラスは省略

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        string S = Console.ReadLine();

        int[] A = new int[N + 1];
        int[] B = new int[N + 1];

        for (int i = 0; i < N; i++)
        {
            A[i + 1] = A[i] + (S[i] == 'A' ? 1 : 0);
            B[i + 1] = B[i] + (S[i] == 'B' ? 1 : 0);
        }

        int[] C = new int[N + 1];
        for (int i = 0; i < N + 1; i++)
            C[i] = A[i] - B[i];

        // C[i] が負数にならないように調整する
        int min = C.Min();
        C = C.Select(_ => _ - min).ToArray();

        int max = C.Max();

        RangeSumQuery counts = new RangeSumQuery(new long[max + 1]);
        for (int i = 0; i < N + 1; i++)
            counts[C[i]]++;

        long ans = 0;
        foreach (var v in C)
        {
            counts[v]--;
            ans += counts.Sum(v + 1, max);
        }
        Console.WriteLine(ans);
    }
}

// RangeSumQuery クラスは省略

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

string S = Console.ReadLine();

int[] A = new int[N + 1];

int[] B = new int[N + 1];

for (int i = 0; i < N; i++)

{

A[i + 1] = A[i] + (S[i] == 'A' ? 1 : 0);

B[i + 1] = B[i] + (S[i] == 'B' ? 1 : 0);

}

int[] C = new int[N + 1];

for (int i = 0; i < N + 1; i++)

C[i] = A[i] - B[i];

// C[i] が負数にならないように調整する

int min = C.Min();

C = C.Select(_ => _ - min).ToArray();

int max = C.Max();

RangeSumQuery counts = new RangeSumQuery(new long[max + 1]);

for (int i = 0; i < N + 1; i++)

counts[C[i]]++;

long ans = 0;

foreach (var v in C)

{

counts[v]--;

ans += counts.Sum(v + 1, max);

}

Console.WriteLine(ans);

}

F – Manhattan Christmas Tree 2

問題の概要

二次元平面上に N 個のクリスマスツリーがあり、i 番目のクリスマスツリーは座標 (X[i], Y[i]) に存在する。

Q 個のクエリを処理せよ。

クエリ 1：i 番目のクリスマスツリーの座標を (x, y) に変更する。
クエリ 2：L 番目から R 番目までのクリスマスツリーのうち、座標 (x, y) からマンハッタン距離で最も遠いクリスマスツリーまでの距離を出力する。

マンハッタン距離で最も遠い点を取得する方法ですが、いわゆる45度回転の処理をおこないます。

(x1, y1) と (x2, y2) のマンハッタン距離は |x1 – x2| + |y1 – y2| です。

|z| は max(z, -z) と考えることができます。
|x1 – x2| + |y1 – y2|
⇔ max(x1 – x2, x2 – x1) + max(y1 – y2, y2 – y1)
⇔ max((x1 – x2) + (y1 – y2), (x1 – x2) + (y2 – y1), (x2 – x1) + (y1 – y2), (x2 – x1) + (y2 – y1))
⇔ max((x1 + y1) – (x2 + y2), (x1 – y1) – (x2 – y2), -(x1 – y1) + (x2 – y2), -(x1 + y1) + (x2 + y2))

ここで x + y = u, x – y = v と置くと max(u1 – u2, v1 – v2, -v1 + v2, -u1 + u2) となり、絶対値を使うなら max(|u1 – u2|, |v1 – v2|) です。x と y が混在する計算式を置き換えることで u のみの式と v のみの式に分離することができました。

座標 (x0, y0) からマンハッタン距離で最も遠い点の距離は max(|U – u0|, |V – v0|) ですが、これは max(|maxU – u|, |maxV – v|, |minU – u|, |minV – v|) と表すことができます。RangeMaxQuery, RangeMinQuery クラスを使えば L 番目から R 番目までの点のうち、座標 (x, y) からマンハッタン距離で最も遠い点までの距離を求めることができます。

// RangeMaxQuery, RangeMinQuery クラスは省略

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int Q) = (nq[0], nq[1]);

        RangeMaxQuery u_max = new RangeMaxQuery(new long[N]);
        RangeMaxQuery v_max = new RangeMaxQuery(new long[N]);
        RangeMinQuery u_min = new RangeMinQuery(new long[N]);
        RangeMinQuery v_min = new RangeMinQuery(new long[N]);

        for (int i = 0; i < N; i++)
        {
            int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            (int x, int y) = (xy[0], xy[1]);
            u_max[i] = x + y;
            v_max[i] = x - y;
            u_min[i] = x + y;
            v_min[i] = x - y;
        }

        List<long> ans = new List<long>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            if (t == 1)
            {
                (int idx, int x, int y) = (query[1] - 1, query[2], query[3]);
                u_max[idx] = x + y;
                v_max[idx] = x - y;
                u_min[idx] = x + y;
                v_min[idx] = x - y;
            }
            if (t == 2)
            {
                (int l, int r, int x, int y) = (query[1] - 1, query[2] - 1, query[3], query[4]);
                int u = x + y;
                int v = x - y;

                long res = 0;
                res = Math.Max(res, Math.Abs(u_max.Max(l, r) - u));
                res = Math.Max(res, Math.Abs(v_max.Max(l, r) - v));
                res = Math.Max(res, Math.Abs(u_min.Min(l, r) - u));
                res = Math.Max(res, Math.Abs(v_min.Min(l, r) - v));
                ans.Add(res);
            }
        }

        foreach (long v in ans)
            Console.WriteLine(v);
    }
}

// RangeMaxQuery, RangeMinQuery クラスは省略

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int Q) = (nq[0], nq[1]);

RangeMaxQuery u_max = new RangeMaxQuery(new long[N]);

RangeMaxQuery v_max = new RangeMaxQuery(new long[N]);

RangeMinQuery u_min = new RangeMinQuery(new long[N]);

RangeMinQuery v_min = new RangeMinQuery(new long[N]);

for (int i = 0; i < N; i++)

{

int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int x, int y) = (xy[0], xy[1]);

u_max[i] = x + y;

v_max[i] = x - y;

u_min[i] = x + y;

v_min[i] = x - y;

}

List<long> ans = new List<long>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

(int idx, int x, int y) = (query[1] - 1, query[2], query[3]);

u_max[idx] = x + y;

v_max[idx] = x - y;

u_min[idx] = x + y;

v_min[idx] = x - y;

}

if (t == 2)

{

(int l, int r, int x, int y) = (query[1] - 1, query[2] - 1, query[3], query[4]);

int u = x + y;

int v = x - y;

long res = 0;

res = Math.Max(res, Math.Abs(u_max.Max(l, r) - u));

res = Math.Max(res, Math.Abs(v_max.Max(l, r) - v));

res = Math.Max(res, Math.Abs(u_min.Min(l, r) - u));

res = Math.Max(res, Math.Abs(v_min.Min(l, r) - v));

ans.Add(res);

}

foreach (long v in ans)

Console.WriteLine(v);

}

F – Starry Landscape Photo

問題の概要

N 個の星が東から西へ一直線上に並んでいる。東から i 番目の星の明るさは B[i] 番目である。

整数の組 (l, r) を選ぶ。東から l 番目の星から r 番目の星のみがフレームに収まるようにカメラを設置する。
整数 b を選び、星の明るさが b 番目までの星のみが写るようにシャッターを開放する。

このようにして撮影された夜空の写真に写っている星の集合としてありえるものが何通りあるか求めよ。

整数 b を 1 から順に増やしていくことを考えます。これによって写真に写る星がひとつずつ増えていくのですが、その星と既存の星の組み合わせの数がいくつあるかを考えてみることにします。

組み合わせの数はその星の左側にある星の数（left）と右側にある星の数（right）から計算できます。(left + 1) × (right + 1) が組み合わせの数です。これはRangeSumQuery クラスを使えば計算できます。

// RangeSumQuery クラスは省略

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        List<(int idx, int v)> pairs = new List<(int idx, int v)>();
        for (int i = 0; i < N; i++)
            pairs.Add((i, A[i]));

        pairs = pairs.OrderBy(_ => _.v).ToList();

        RangeSumQuery counts = new RangeSumQuery(new long[N]);

        long ans = 0;
        foreach (var pair in pairs)
        {
            counts[pair.idx] = 1;
            long l = counts.Sum(0, pair.idx - 1);
            long r = counts.Sum(pair.idx + 1, N - 1);
            ans += (l + 1) * (r + 1);
        }
        Console.WriteLine(ans);
    }
}

// RangeSumQuery クラスは省略

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

List<(int idx, int v)> pairs = new List<(int idx, int v)>();

for (int i = 0; i < N; i++)

pairs.Add((i, A[i]));

pairs = pairs.OrderBy(_ => _.v).ToList();

RangeSumQuery counts = new RangeSumQuery(new long[N]);

long ans = 0;

foreach (var pair in pairs)

{

counts[pair.idx] = 1;

long l = counts.Sum(0, pair.idx - 1);

long r = counts.Sum(pair.idx + 1, N - 1);

ans += (l + 1) * (r + 1);

}

Console.WriteLine(ans);

}

E – Clamp

問題の概要

長さ N の整数列 A が与えられる。
Q 個のクエリを処理せよ。

クエリ 1：A[x] の値を y に変更する。
クエリ 2：B[i] = max(l, min(r, A[i])) と定義したとき B の総和を求める。

B[i] の値は以下のようになります。

① l < r のとき
A[i] ≦ l ⇒ B[i] = l、A[i] ≧ r ⇒ B[i] = r、それ以外 ⇒ B[i] = A[i]

② それ以外のとき
常に B[i] = l

① を計算するには A[i] の値が v である i の個数を管理します。

counts[v]：A[i] の値が v である i の個数
sums[v]：A[i] の値が v である A[i] の総和

RangeSumQuery クラスを使えば l 以下の要素の個数、r 以上の要素の個数、l より大きく r より小さい要素の総和を計算することができます。

// RangeSumQuery クラスは省略

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int Q) = (nq[0], nq[1]);

        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int max = 500010;
        RangeSumQuery counts = new RangeSumQuery(new long[max]);
        RangeSumQuery sums = new RangeSumQuery(new long[max]);

        foreach (int v in A)
        {
            counts[v]++;
            sums[v] += v;
        }

        List<long> ans = new List<long>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            if (t == 1)
            {
                (int x, int y) = (query[1] - 1, query[2]);
                int old_v = A[x];
                A[x] = y;
                int new_v = A[x];
                counts[old_v]--;
                counts[new_v]++;
                sums[old_v] -= old_v;
                sums[new_v] += new_v;
            }
            if (t == 2)
            {
                (int l, int r) = (query[1], query[2]);
                if (r <= l)
                    ans.Add(1L * l * N);
                else
                    ans.Add(sums.Sum(l + 1, r - 1) + counts.Sum(0, l) * l + counts.Sum(r, max - 1) * r);
            }
        }

        foreach (long v in ans)
            Console.WriteLine(v);
    }
}

// RangeSumQuery クラスは省略

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int Q) = (nq[0], nq[1]);

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int max = 500010;

RangeSumQuery counts = new RangeSumQuery(new long[max]);

RangeSumQuery sums = new RangeSumQuery(new long[max]);

foreach (int v in A)

{

counts[v]++;

sums[v] += v;

}

List<long> ans = new List<long>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

(int x, int y) = (query[1] - 1, query[2]);

int old_v = A[x];

A[x] = y;

int new_v = A[x];

counts[old_v]--;

counts[new_v]++;

sums[old_v] -= old_v;

sums[new_v] += new_v;

}

if (t == 2)

{

(int l, int r) = (query[1], query[2]);

if (r <= l)

ans.Add(1L * l * N);

else

ans.Add(sums.Sum(l + 1, r - 1) + counts.Sum(0, l) * l + counts.Sum(r, max - 1) * r);

}

foreach (long v in ans)

Console.WriteLine(v);

}

E – Alternating String

問題の概要

0 と 1 のみからなる長さ N の文字列 S が与えられる。
Q 個のクエリを処理せよ。

クエリ 1：S の L 文字目から R 文字目までの 0 と 1 を反転させる。
クエリ 2：S の L 文字目から R 文字目までを抜き出した部分文字列において、どの連続する 2 文字も異なるのであれば “Yes”、そうでないなら “No” と出力する。

文字列の先頭に番兵 ‘X’ を追加します。そして A[i] を S[i] == S[i + 1] なら 1、そうでないなら 0 と定義します。

L 文字目から R 文字目までの 0 と 1 を反転させた場合、A の値が変更されるのは A[L – 1] と A[R] だけです。

また L 文字目から R 文字目（L < R）までを抜き出した部分文字列において、連続する 2 文字が同じである部分があるなら閉区間 [L, R – 1] における A の最大値は 1 であり、そうでないなら 0 です（L == R のときは常に答えは “Yes” になるので注意すること）。

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        (int N, int Q) = (nq[0], nq[1]);

        string S = Console.ReadLine();
        S = 'X' + S;

        RangeMaxQuery rsq = new RangeMaxQuery(new long[N + 1]);

        for (int i = 0; i < N; i++)
            rsq[i] = S[i] == S[i + 1] ? 1 : 0;

        List<string> ans = new List<string>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            (int t, int l, int r) = (query[0], query[1], query[2]);
            if (t == 1)
            {
                rsq[l - 1] = rsq[l - 1] == 0 ? 1 : 0;
                rsq[r] = rsq[r] == 0 ? 1 : 0;
            }
            if (t == 2)
            {
                if (l == r)
                    ans.Add("Yes");
                else
                    ans.Add(rsq.Max(l, r - 1) == 0 ? "Yes" : "No");
            }
        }

        foreach (string str in ans)
            Console.WriteLine(str);
    }
}

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int N, int Q) = (nq[0], nq[1]);

string S = Console.ReadLine();

S = 'X' + S;

RangeMaxQuery rsq = new RangeMaxQuery(new long[N + 1]);

for (int i = 0; i < N; i++)

rsq[i] = S[i] == S[i + 1] ? 1 : 0;

List<string> ans = new List<string>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

(int t, int l, int r) = (query[0], query[1], query[2]);

if (t == 1)

{

rsq[l - 1] = rsq[l - 1] == 0 ? 1 : 0;

rsq[r] = rsq[r] == 0 ? 1 : 0;

}

if (t == 2)

{

if (l == r)

ans.Add("Yes");

else

ans.Add(rsq.Max(l, r - 1) == 0 ? "Yes" : "No");

}

foreach (string str in ans)

Console.WriteLine(str);

}

AtCoder NoviStepsを埋めてみる(35) セグメント木（segment tree）1D

D – Flat Subsequence

B58 – Jumping

037 – Don’t Leave the Spice（★5）

Q – Flowers

F – Second Largest Query

F – Parenthesis Checking

B59 – Number of Inversions

F – Double Sum

J – Segment Tree

F – Insert

E – A > B substring

F – Manhattan Christmas Tree 2

F – Starry Landscape Photo

E – Clamp

E – Alternating String

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ