AVL木で区間を管理する

一直線状に並んだ区間の集合は、AVL木を用いることで、効率的に管理することができます。

Contents

1 E – Cover query
2 E – 1D Bucket Tool

E – Cover query

問題の趣旨は以下のとおりです。

Q 回にわたって L と R が与えられるので L 番目のマスから R 番目までのマスを黒く塗る。
そのあと黒く塗られているマスの数を出力せよ。

半開区間 [left, right) をAVL木に格納して新しい半開区間が格納されようとしたときに既存の半開区間とマージできるならマージする処理を繰り返すことで解を得ることができます。

新しい半開区間 [left, right) と既存の半開区間 [old_left, old_right) がまったく重なっていないのであればそのまま追加し、一部または全部が重なっているのであれば既存の半開区間は取り除いて新しい区間の left と right の値を調整して追加することで区間をマージする処理をおこないます。

既存の半開区間から left ≦ old_left である最小のものを探します。みつかったら old_left が right 以下であるか調べます。もしそうなら削除し、新しく追加しようとしている半開区間の left と right を left = min(left, old_left), right = max(right, old_right) と更新し、もう一度この処理を繰り返します。そうでない場合や要素そのものが見つからない場合は処理を終了します。

次に既存の半開区間から old_left ≦ right である最大のものを探します。みつかったら old_right が left 以上であるか調べます。もしそうなら削除し、新しく追加しようとしている半開区間の left と right を left = min(left, old_left), right = max(right, old_right) と更新し、もう一度この処理を繰り返します。そうでない場合や要素そのものが見つからない場合は処理を終了します。

削除すべき既存の半開区間を削除したら新しい半開区間を追加します。削除された区間の長さと新たに追加された区間の長さの差分をみれば解を得ることができます。

class Program
{
    static (int, int) ReadInt2()
    {
        string[] vs = Console.ReadLine().Split();
        return (int.Parse(vs[0]), int.Parse(vs[1]));
    }

    // 半開区間の両端の値と区間の長さ
    class LR
    {
        public LR(long left, long right)
        {
            L = left;
            R = right;
            Length = right - left;
        }
        public long L = 0;
        public long R = 0;
        public long Length = 0;
    }

    static void Main()
    {
        (int N, int Q) = ReadInt2();

        AvlTree avl = new AvlTree();

        // 左の値から半開区間の情報を取得できるようにする
        Dictionary<long, LR> dic = new Dictionary<long, LR>();

        long length = 0; // 区間の長さの総和（黒で塗られているマスの個数）
        for (int i = 0; i < Q; i++)
        {
            (long left, long right) = ReadInt2();
            right++; // 半開区間なので 1 を足す

            // AVL木から値を削除すると同時に
            // left, right, length の更新、辞書からの削除もまとめておこなう
            void RemoveLeft(long old_left)
            {
                avl.Remove(old_left);
                left = Math.Min(left, old_left);
                right = Math.Max(right, dic[old_left].R);
                length -= dic[old_left].Length;
                dic.Remove(old_left);
            }

            // 取り除くべき既存の半開区間を取り除く
            while (true)
            {
                List<long> vs = avl.GetOvers(left, true, 1);
                if (vs.Count > 0 && right >= vs[0])
                    RemoveLeft(vs[0]);
                else
                    break;
            }
            while (true)
            {
                List<long> vs = avl.GetUnders(right, true, 1);
                if (vs.Count > 0 && left <= dic[vs[0]].R)
                    RemoveLeft(vs[0]);
                else
                    break;
            }

            // 新しい半開区間を追加
            avl.Add(left);
            LR lr = new LR(left, right);
            dic.Add(left, lr);
            length += lr.Length;

            Console.WriteLine(N - length);
        }
    }
}

class Program

{

static (int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

// 半開区間の両端の値と区間の長さ

class LR

{

public LR(long left, long right)

{

L = left;

R = right;

Length = right - left;

}

public long L = 0;

public long R = 0;

public long Length = 0;

}

static void Main()

{

(int N, int Q) = ReadInt2();

AvlTree avl = new AvlTree();

// 左の値から半開区間の情報を取得できるようにする

Dictionary<long, LR> dic = new Dictionary<long, LR>();

long length = 0; // 区間の長さの総和（黒で塗られているマスの個数）

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

{

(long left, long right) = ReadInt2();

right++; // 半開区間なので 1 を足す

// AVL木から値を削除すると同時に

// left, right, length の更新、辞書からの削除もまとめておこなう

void RemoveLeft(long old_left)

{

avl.Remove(old_left);

left = Math.Min(left, old_left);

right = Math.Max(right, dic[old_left].R);

length -= dic[old_left].Length;

dic.Remove(old_left);

}

// 取り除くべき既存の半開区間を取り除く

while (true)

{

List<long> vs = avl.GetOvers(left, true, 1);

if (vs.Count > 0 && right >= vs[0])

RemoveLeft(vs[0]);

else

break;

}

while (true)

{

List<long> vs = avl.GetUnders(right, true, 1);

if (vs.Count > 0 && left <= dic[vs[0]].R)

RemoveLeft(vs[0]);

else

break;

}

// 新しい半開区間を追加

avl.Add(left);

LR lr = new LR(left, right);

dic.Add(left, lr);

length += lr.Length;

Console.WriteLine(N - length);

}

E – 1D Bucket Tool

問題の趣旨は以下のとおりです。

クエリタイプ 1 では指定されたマスと繋がっている同じ色のマスをすべて指定された色に塗り直す。
クエリタイプ 2 では指定された色のマスの個数を出力する。

上の問題と似ていますが、マージしてよいのは接している同じ色の区間だけです。なので区間の色も記録する必要があります。

LRクラスを以下のように定義します。今回は Length をフィールド変数にするのではなく、L と R を変更したときに区間の長さが自動的に再計算されるようにプロパティとして定義します。

class LR
{
    public LR(long left, long right, int color)
    {
        L = left;
        R = right;
        Color = color;
    }
    public long Length
    {
        get { return R - L; }
    }

    public long L = 0;
    public long R = 0;
    public int Color = 0;
}

class LR

{

public LR(long left, long right, int color)

{

L = left;

R = right;

Color = color;

}

public long Length

{

get { return R - L; }

}

public long L = 0;

public long R = 0;

public int Color = 0;

}

半開区間の色が変わったらその前後にある区間の色を調べます。同じ色であればマージします。半開区間は left の値で管理しているので、マージするときは ① nextをcurにマージさせる、② curをprevにマージさせるという順番でやったほうがわかりやすいです。

class Program
{
    static (int, int) ReadInt2()
    {
        string[] vs = Console.ReadLine().Split();
        return (int.Parse(vs[0]), int.Parse(vs[1]));
    }

    static int[] ReadIntArray()
    {
        return Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
    }

    static void Main()
    {
        (int N, int Q) = ReadInt2();
        long[] counts = new long[N + 1];

        AvlTree avl = new AvlTree();

        Dictionary<long, LR> dic = new Dictionary<long, LR>();

        // 初期状態は半開区間 [i, i + 1) の色は i
        for (int i = 1; i <= N; i++)
        {
            avl.Add(i);
            dic.Add(i, new LR(i, i + 1, i));
            counts[i] = 1;
        }

        for (int i = 0; i < Q; i++)
        {
            int[] vs = ReadIntArray();
            int t = vs[0];
            if (t == 1)
            {
                int x = vs[1];
                int c = vs[2];

                List<long> vs1 = avl.GetUnders(x, true, 2);
                List<long> vs2 = avl.GetOvers(x, false, 1);

                LR cur = dic[vs1[0]]; // x が属する半開区間 (cur)
                LR prev = vs1.Count >= 2 ? dic[vs1[1]] : null; // そのひとつ前
                LR next = vs2.Count >= 1 ? dic[vs2[0]] : null; // そのひとつ後

                // 半開区間の色を変更する（区間の長さだけ前の色の個数は減らし新しい色を増やす）
                counts[cur.Color] -= cur.Length;
                cur.Color = c;
                counts[cur.Color] += cur.Length;

                // cur の右側に同じ色の半開区間があるならマージする
                // next は削除して next.Length だけ cur.Length を伸ばす
                if (next != null && next.Color == c)
                {
                    avl.Remove(next.L);
                    dic.Remove(next.L);
                    cur.R = next.R;
                }

                // cur の左側に同じ色の半開区間があるならマージする
                // cur は削除して cur.Length だけ prev.Length を伸ばす
                if (prev != null && prev.Color == c)
                {
                    avl.Remove(cur.L);
                    dic.Remove(cur.L);
                    prev.R = cur.R;
                }
            }
            if (t == 2)
            {
                int c = vs[1];
                Console.WriteLine(counts[c]);
            }
        }
    }
}

class Program

{

static (int, int) ReadInt2()

{

string[] vs = Console.ReadLine().Split();

return (int.Parse(vs[0]), int.Parse(vs[1]));

}

static int[] ReadIntArray()

{

return Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

}

static void Main()

{

(int N, int Q) = ReadInt2();

long[] counts = new long[N + 1];

AvlTree avl = new AvlTree();

Dictionary<long, LR> dic = new Dictionary<long, LR>();

// 初期状態は半開区間 [i, i + 1) の色は i

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

{

avl.Add(i);

dic.Add(i, new LR(i, i + 1, i));

counts[i] = 1;

}

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

{

int[] vs = ReadIntArray();

int t = vs[0];

if (t == 1)

{

int x = vs[1];

int c = vs[2];

List<long> vs1 = avl.GetUnders(x, true, 2);

List<long> vs2 = avl.GetOvers(x, false, 1);

LR cur = dic[vs1[0]]; // x が属する半開区間 (cur)

LR prev = vs1.Count >= 2 ? dic[vs1[1]] : null; // そのひとつ前

LR next = vs2.Count >= 1 ? dic[vs2[0]] : null; // そのひとつ後

// 半開区間の色を変更する（区間の長さだけ前の色の個数は減らし新しい色を増やす）

counts[cur.Color] -= cur.Length;

cur.Color = c;

counts[cur.Color] += cur.Length;

// cur の右側に同じ色の半開区間があるならマージする

// next は削除して next.Length だけ cur.Length を伸ばす

if (next != null && next.Color == c)

{

avl.Remove(next.L);

dic.Remove(next.L);

cur.R = next.R;

}

// cur の左側に同じ色の半開区間があるならマージする

// cur は削除して cur.Length だけ prev.Length を伸ばす

if (prev != null && prev.Color == c)

{

avl.Remove(cur.L);

dic.Remove(cur.L);

prev.R = cur.R;

}

if (t == 2)

{

int c = vs[1];

Console.WriteLine(counts[c]);

}

E – Cover query

E – 1D Bucket Tool

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

コメントについて

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

コメントをどうぞ