ABC470-D Inverse and Swap

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 5");
            WillReturn.Add("2 1 3 5 4");
            WillReturn.Add("1 2 4");
            WillReturn.Add("2");
            WillReturn.Add("1 2 3");
            WillReturn.Add("1 3 4");
            WillReturn.Add("2");
            //4 5 2 1 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 4");
            WillReturn.Add("3 7 5 6 4 2 1");
            WillReturn.Add("2");
            WillReturn.Add("2");
            WillReturn.Add("2");
            WillReturn.Add("2");
            //3 7 5 6 4 2 1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 8");
            WillReturn.Add("7 3 2 4 8 5 10 9 1 6");
            WillReturn.Add("2");
            WillReturn.Add("1 4 10");
            WillReturn.Add("1 6 9");
            WillReturn.Add("2");
            WillReturn.Add("1 9 10");
            WillReturn.Add("1 3 10");
            WillReturn.Add("2");
            WillReturn.Add("1 4 6");
            //3 10 2 8 6 7 1 5 9 4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] PArr = GetSplitArr(InputList[1]);

        // 値[Ind]なDict
        var Dict1 = new Dictionary<long, long>();

        // Ind[値]なDict
        var Dict2 = new Dictionary<long, long>();

        for (long I = 0; I <= PArr.GetUpperBound(0); I++) {
            Dict1[I + 1] = PArr[I];
            Dict2[PArr[I]] = I + 1;
        }

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long Type = wkArr[0];
            if (Type == 1) {
                long PrevInd = wkArr[1];
                long NextInd = wkArr[2];

                long PrevVal = Dict1[PrevInd];
                long NextVal = Dict1[NextInd];

                long tmp1 = Dict1[PrevInd];
                Dict1[PrevInd] = Dict1[NextInd];
                Dict1[NextInd] = tmp1;

                long tmp2 = Dict2[PrevVal];
                Dict2[PrevVal] = Dict2[NextVal];
                Dict2[NextVal] = tmp2;
            }
            if (Type == 2) {
                var wkPointer = Dict1;
                Dict1 = Dict2;
                Dict2 = wkPointer;
            }
        }

        var Answer = new List<long>();
        foreach (var EachPair in Dict1.OrderBy(pX => pX.Key)) {
            Answer.Add(EachPair.Value);
        }
        Console.WriteLine(LongEnumJoin(" ", Answer));
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

解説

値[添字]なDictと、添字[値]なDictを用意
クエリ1はナイーブに更新
クエリ2はDict同士をswap

で解けます。