第4回PAST K 転倒数

問題へのリンク

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("2");
            WillReturn.Add("3");
            WillReturn.Add("1 3 2");
            WillReturn.Add("2");
            WillReturn.Add("5 4");
            WillReturn.Add("2");
            WillReturn.Add("1 2");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("8");
            WillReturn.Add("16 6 15 10 18 13 17 11");
            WillReturn.Add("13");
            WillReturn.Add("4 10 6 4 14 17 13 9 3 9 4 8 14");
            WillReturn.Add("11");
            WillReturn.Add("11 17 12 3 13 8 10 11 18 2 19");
            WillReturn.Add("10");
            WillReturn.Add("18 11 16 19 4 17 7 3 5 8");
            WillReturn.Add("3");
            WillReturn.Add("3 10 9");
            WillReturn.Add("13");
            WillReturn.Add("8 17 20 8 20 1 5 17 4 16 18 20 4");
            WillReturn.Add("15");
            WillReturn.Add("11 2 1 16 8 17 4 7 3 6 4 13 16 16 16");
            WillReturn.Add("2");
            WillReturn.Add("12 12");
            WillReturn.Add("8");
            WillReturn.Add("7 14 7 5 8 17 19 4");
            WillReturn.Add("15");
            WillReturn.Add("3 6 1 16 11 5 3 15 9 15 12 15 5 19 7");
            WillReturn.Add("20");
            WillReturn.Add("4 3 7 6 1 8 2 3 9 8 6 3 10 9 7 7 3 2 2 10");
            //12430
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000000;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long K = int.Parse(InputList[0]);

        var AArrList = new List<long[]>();

        int CurrInd = 0;
        for (long I = 1; I <= K; I++) {
            CurrInd += 2;
            AArrList.Add(InputList[CurrInd].Split(' ').Select(pX => long.Parse(pX)).ToArray());
        }

        long[] QArr = InputList.Last().Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 度数分布表
        long[] AllCntArr = new long[20 + 1];

        // 件数を事前に集計しておく
        long[,] CntArr = new long[K + 1, 20 + 1];
        for (int I = 0; I <= AArrList.Count - 1; I++) {
            foreach (long EachInt in AArrList[I]) {
                CntArr[I, EachInt]++;
                CntArr[I, EachInt] %= Hou;
            }
        }

        var InvDict = new Dictionary<long, long>();

        long Answer = 0;
        foreach (int EachQ in QArr) {
            long[] CurrArr = AArrList[EachQ - 1];

            if (InvDict.ContainsKey(EachQ) == false) {
                InvDict[EachQ] = DeriveInvCnt(CurrArr);
            }
            Answer += InvDict[EachQ];
            Answer %= Hou;

            // 逆方向の累積和を求めておく
            long[] RevRunSumArr = new long[20 + 1];
            for (long I = 20; 0 <= I; I--) {
                RevRunSumArr[I] = AllCntArr[I];
                if (I < 20) {
                    RevRunSumArr[I] += RevRunSumArr[I + 1];
                }
                RevRunSumArr[I] %= Hou;
            }

            for (long I = 1; I <= 20; I++) {
                if (I < 20) {
                    Answer += RevRunSumArr[I + 1] * CntArr[EachQ - 1, I];
                    Answer %= Hou;
                }
                AllCntArr[I] += CntArr[EachQ - 1, I];
                AllCntArr[I] %= Hou;
            }
        }
        Console.WriteLine(Answer);
    }

    // 配列を引数として、配列内での転倒数を返す
    static long DeriveInvCnt(long[] pArr)
    {
        long WillReturn = 0;
        var Ins_Fenwick_Tree = new Fenwick_Tree(20);

        foreach (int EachInt in pArr) {
            long Cnt = Ins_Fenwick_Tree.GetSum(EachInt + 1, 20, false);
            WillReturn += Cnt;
            WillReturn %= Hou;
            Ins_Fenwick_Tree.Add(EachInt, 1, false);
        }
        return WillReturn;
    }
}

#region Fenwick_Tree
// フェニック木
internal class Fenwick_Tree
{
    private long[] mBitArr;
    private long mN;

    // コンストラクタ
    internal Fenwick_Tree(long pItemCnt)
    {
        mN = pItemCnt;
        mBitArr = new long[pItemCnt + 1];
    }

    // [pSta,pEnd] のSumを返す
    internal long GetSum(long pSta, long pEnd, bool pIsZeroOrigin)
    {
        return GetSum(pEnd, pIsZeroOrigin) - GetSum(pSta - 1, pIsZeroOrigin);
    }

    // [0,pEnd] のSumを返す
    internal long GetSum(long pEnd, bool pIsZeroOrigin)
    {
        if (pIsZeroOrigin) {
            pEnd++; // 1オリジンに変更
        }

        long Sum = 0;
        while (pEnd >= 1) {
            Sum += mBitArr[pEnd];
            pEnd -= pEnd & -pEnd;
        }
        return Sum;
    }

    // [I] に Xを加算
    internal void Add(long pI, long pX, bool pIsZeroOrigin)
    {
        if (pIsZeroOrigin) {
            pI++; // 1オリジンに変更
        }

        while (pI <= mN) {
            mBitArr[pI] += pX;
            pI += pI & -pI;
        }
    }
}
#endregion

解説

前処理で
数列ごとの度数分布表と
数列ごとの転倒数を求めてます。

数列を結合した時の転倒数の増加は、
度数分布表を使って高速に求めることができます。