ABC442-E Laser Takahashi

問題へのリンク

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 4");
            WillReturn.Add("0 1");
            WillReturn.Add("1 -2");
            WillReturn.Add("1 0");
            WillReturn.Add("-2 0");
            WillReturn.Add("3 0");
            WillReturn.Add("4 1");
            WillReturn.Add("1 4");
            WillReturn.Add("5 4");
            WillReturn.Add("3 5");
            //2
            //5
            //4
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1");
            WillReturn.Add("1 2");
            WillReturn.Add("1 2");
            WillReturn.Add("1 2");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8 10");
            WillReturn.Add("-84 -60");
            WillReturn.Add("-100 8");
            WillReturn.Add("77 55");
            WillReturn.Add("-14 -10");
            WillReturn.Add("50 -4");
            WillReturn.Add("-63 -45");
            WillReturn.Add("26 -17");
            WillReturn.Add("-7 -5");
            WillReturn.Add("3 7");
            WillReturn.Add("2 4");
            WillReturn.Add("8 4");
            WillReturn.Add("8 4");
            WillReturn.Add("7 1");
            WillReturn.Add("1 7");
            WillReturn.Add("6 3");
            WillReturn.Add("4 7");
            WillReturn.Add("4 5");
            WillReturn.Add("2 6");
            //3
            //8
            //4
            //4
            //5
            //8
            //6
            //8
            //7
            //8
        }
        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();
    }

    class MonsterDef : IComparable<MonsterDef>
    {
        internal long ID;
        internal long X;
        internal long Y;
        internal long Syougen;
        internal long DenseRank;

        public int CompareTo(MonsterDef pOtherIns)
        {
            // 第1ソートキーは象限
            if (Syougen != pOtherIns.Syougen) {
                return Syougen.CompareTo(pOtherIns.Syougen);
            }

            // 第2ソートキーはTangent
            if (Syougen % 2 == 1) {
                PointDef pA;
                PointDef pB;
                pA.X = X;
                pA.Y = Y;
                pB.X = pOtherIns.X;
                pB.Y = pOtherIns.Y;

                // Tangentでの降順なのでマイナスをかける
                return CompareTangent(pA, pB) * (-1);
            }
            return 0;
        }

        // --------------------------------------------------------
        // (静的メソッド)ソート済のListを引数として、dense_rankを設定
        // --------------------------------------------------------
        static internal void SetDenseRank(List<MonsterDef> pMonsterList)
        {
            long CurrDenseRank = 1;
            for (int I = 0; I <= pMonsterList.Count - 1; I++) {
                // 前と違ったらインクリメント
                if (I > 0) {
                    int Result = pMonsterList[I].CompareTo(pMonsterList[I - 1]);
                    if (Result != 0) {
                        CurrDenseRank++;
                    }
                }
                pMonsterList[I].DenseRank = CurrDenseRank;
            }
        }
    }
    static List<MonsterDef> mMonsterList = new List<MonsterDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        long N = wkArr[0];

        long CurrID = 0;
        foreach (string EachStr in InputList.Skip(1).Take((int)N)) {
            SplitAct(EachStr);
            var WillAdd = new MonsterDef();
            WillAdd.ID = ++CurrID;
            long X = wkArr[0];
            long Y = wkArr[1];
            WillAdd.X = X;
            WillAdd.Y = Y;

            // 時計の0時から時計周りでの採番
            long Syougen = 0;
            if (X == 0 && Y > 0) Syougen = 0;
            if (X > 0 && Y > 0) Syougen = 1;
            if (X > 0 && Y == 0) Syougen = 2;
            if (X > 0 && Y < 0) Syougen = 3;

            if (X == 0 && Y < 0) Syougen = 4;
            if (X < 0 && Y < 0) Syougen = 5;
            if (X < 0 && Y == 0) Syougen = 6;
            if (X < 0 && Y > 0) Syougen = 7;

            WillAdd.Syougen = Syougen;
            mMonsterList.Add(WillAdd);
        }
        mMonsterList.Sort();
        MonsterDef.SetDenseRank(mMonsterList);

        // DenseRankの最大値を求める
        long MaxDenseRank = mMonsterList.Max(pX => pX.DenseRank);

        // 個数[DenseRank]なフェニック木
        var Ins_Fenwick_Tree = new Fenwick_Tree(MaxDenseRank);
        foreach (MonsterDef EachMonster in mMonsterList) {
            Ins_Fenwick_Tree[EachMonster.DenseRank]++;
        }

        // DenseRank[モンスターID]なDict
        var DenseRankDict = new Dictionary<long, long>();
        foreach (MonsterDef EachMonster in mMonsterList) {
            DenseRankDict[EachMonster.ID] = EachMonster.DenseRank;
        }

        foreach (string EachStr in InputList.Skip((int)N + 1)) {
            SplitAct(EachStr);
            long Sta = wkArr[0];
            long End = wkArr[1];

            long StaDenseRank = DenseRankDict[Sta];
            long EndDenseRank = DenseRankDict[End];
            if (StaDenseRank <= EndDenseRank) {
                long Answer = Ins_Fenwick_Tree.GetSum(StaDenseRank, EndDenseRank);
                Console.WriteLine(Answer);
            }
            else {
                // 補集合で計算
                long Answer = N - Ins_Fenwick_Tree.GetSum(EndDenseRank, StaDenseRank);
                Answer += Ins_Fenwick_Tree[StaDenseRank];
                Answer += Ins_Fenwick_Tree[EndDenseRank];
                Console.WriteLine(Answer);
            }
        }
    }

    struct PointDef
    {
        internal long X;
        internal long Y;
    }

    // Tangentの大小関係での比較結果を返す
    static int CompareTangent(PointDef pA, PointDef pB)
    {
        if (pA.X == 0 && pB.X == 0) return 0;
        if (pA.X == 0 && pB.X != 0) return 1;
        if (pA.X != 0 && pB.X == 0) return -1;

        return (pA.Y * pB.X).CompareTo(pB.Y * pA.X);
    }
}

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

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタ(外部配列のUBのみ指定)
    internal Fenwick_Tree(long pExternalArrUB)
    {
        mExternalArrUB = pExternalArrUB;

        // フェニック木の外部配列は0オリジンで、
        // フェニック木の内部配列は1オリジンなため、2を足す
        mBitArr = new long[pExternalArrUB + 2];
    }

    // コンストラクタ(初期化用の配列指定)
    internal Fenwick_Tree(long[] pArr)
        : this(pArr.GetUpperBound(0))
    {
        for (long I = 0; I <= pArr.GetUpperBound(0); I++) {
            this.Add(I, pArr[I]);
        }
    }

    // コンストラクタ(初期化用のList指定)
    internal Fenwick_Tree(List<long> pList)
        : this(pList.Count - 1)
    {
        for (int I = 0; I <= pList.Count - 1; I++) {
            this.Add(I, pList[I]);
        }
    }

    // インデクサ
    internal long this[long pInd]
    {
        get { return GetSum(pInd, pInd); }
        set { Add(pInd, value - GetSum(pInd, pInd)); }
    }

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

    // [0,pEnd] のSumを返す
    internal long GetSum(long pEnd)
    {
        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)
    {
        pI++; // 1オリジンに変更

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

解説

まず、受験算数の時計算を意識して時計周りで
象限番号を割り振ります。

後は、
第1ソートキーを象限
第2ソートキーをTangent
としたソートで
SQLのdense_rankな連番を振り
個数[dense_rank]なフェニック木を用意し、
区間和を高速に求めてます。

大小関係が逆転した区間和は、補集合を使って求めるてます。