AGC 005 B - Minimum Sum - バイトの競プロメモ

解法

5 1 4 8 2 6 7 3
たとえば2がminで選ばれる回数は、Lが4,8,2の時でかつRが2,6,7の時なので9回ある。つまり、自分より大きくて左右で地続きになっているものの個数が分かれば解ける。

初めは数を大きい順に見ていき、union-find木に入れて地続きになっているサイズを図って解こうとしたが、もっといい方法があった。
自分より小さく、左右で最も自分に近い数の位置が分かればよかった。

TreeSetに小さい順に数のインデックスを渡せば、higher,lowerで簡単に求まる。

問題の芯
数列問題はとりあえずインデックスを取りたい
aかつbな物を調べたい時は、aな物を一旦集めてその中からbを満たすものを探したい。
（a:自分より小さい b:最も自分に近い数の位置
自分より小さい数をTreeSetに入れて、その中で最も自分に近い数の位置を探せばいい）

public static void main(String[] args)
    {
        N = sc.nextInt();
        A = sc.nextIntArray(N);
        int[] rev = new int[N+1];//１から
        for (int i = 0; i < N; i++)
        {
            rev[A[i]] = i;
        }

        TreeSet<Integer> nums = new TreeSet<>();
        nums.add(-1);
        nums.add(N);

        long sum = 0;
        for (int i = 1; i < N+1; i++)
        {
            int revIndex = rev[i];
            nums.add(revIndex);
            int l = revIndex - nums.lower(revIndex);
            int r = nums.higher(revIndex) - revIndex;
            sum += (long)l * r * i;
        }
        System.out.println(sum);

    }