白準不満ソート(5012)

クレームのソート
1.ヒント
1)区間和を表すセグメントツリーからInversionの個数を算出できる.
2)aiのバージョンは何ですか. aj(ai>aj,i>j)a_i,\a_j(a_i > a_j, i > j)ai​, ak(aj>ak)a k(aj>a k)ak(aj>ak) aj, aka_i,\a_j,\a_kai​, aj​, akは条件を満たす.
3)I[i]I[i]I[i]はどんなバージョンですか(ai, aj)(a_i,\a_j)(ai​, aj)では、S[i]S[i]S[i]S[i]S[i]をaja jajのInversionの個数として定義すれば、Inversionを求める方式と同様に、それを求めることもできる.
2.近接
似たような問題を解いたことがありますか.
白駿バブルセット(1517)
Bubble Sotは隣接する2つの要素のソート方法を変更し、3つの要素を選択する方法はどうですか?
問題の条件が似ているので,Inversionを解く過程に近似できる.
順序を強制できますか?
[x]=S[x]I[x]=S[x]I[x]=S[x]が持つInversion数
定義しようでも、ai、 aja_i,\a_jai​, ajペアでは、S[x]S[x]S[x]がaja jajであるからといって、数を繰り返さないでください.
すなわち、I[x]I[x]I[x]I[x]は、SSSにおいてS[x]S[x]S[x]S[x]S[x]よりも大きい順対の個数である.
例えば、N=4、S=[3,2,1]N=4、S=[3,2,1]N=4、S=[3,2,1]の場合、I=[0,0,2,3]I=[0,0,2,3]I=[0,2,3]I=[0,3,0,2,3]I=[0,0,2,3]I=[0,3,3]I=[0,0,0,2,3]となる.
さらにaka kakを加えて、私たちが要求したい3つの要素を求めます.S[k]S[k]S[k]S[k]S[k]と比較して,左のInversionの個数を加算することで,条件を満たす順序対の個数を求めることができる.可能な限り、最小のS[k]S[k]S[k]S[k]S[k]S[k]S[k]S[k]S[k]から探すべきです.2つの要素の値が同じ場合があるので、同じ要素のうちより左側からチェックします.
3.実施

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] S = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		// P[x] = S의 원소 x의 위치 (작은 순으로)  
		ArrayList<PriorityQueue<Integer>> P = new ArrayList<>();
		for (int i = 0; i <= N; i++) P.add(new PriorityQueue<>());
		for (int i = 0; i < N; i++) P.get(S[i]).add(i + 1);
		long[] I = new long[N + 1]; // S[i]가 가지고 있는 Inversion의 개수 저장
		FenwickTree t = new FenwickTree(N); // S[i]가 존재하는지 여부
		for (int i = 1; i <= N; i++) t.add(i, 1);
		// I[i]를 만든다
		for (int i = 1; i <= N; i++) {
			PriorityQueue<Integer> pq = P.get(i);
			// PriorityQueue를 순회하기 위해 임시로 만듬
			PriorityQueue<Integer> temp = new PriorityQueue<>();
			while (!pq.isEmpty()) {
				int x = pq.poll();
				// t에 남아있는 모든 원소는 S[x]보다 같거나 크고,
				// 같은 원소들은 S[x]보다 오른쪽에 있으므로
				// 구간 합 t[x] - 1은 Inversion의 개수가 된다.
				I[x] = t.sum(x) - 1;
				t.add(x, -1);
				temp.offer(x);
			}
			P.set(i, temp);
		}
		long sum = 0;
		t = new FenwickTree(N);
		for (int i = 1; i <= N; i++) t.add(i, I[i]);
		for (PriorityQueue<Integer> pq : P) {
			while (!pq.isEmpty()) {
				int x = pq.poll();
				sum += t.sum(x - 1);
				t.add(x, -(t.sum(x) - t.sum(x - 1)));
			}
		}
		System.out.println(sum);
	}
	
}

class FenwickTree {
	long[] tree;
	
	FenwickTree(int n) { tree = new long[n + 1]; }
	
	void add(int pos, long val) {
		while (pos < tree.length) {
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}
	
	long sum(int pos) {
		long ret = 0;
		while (pos > 0) {
			ret += tree[pos];
			pos -= (pos & -pos);
		}
		return ret;
	}
	
}

1)時間複雑度
NNN個の要素に対してlgnlgnlgn演算を行うのでO(Nlgn)O(Nlgn)O(Nlgn)
2)テストケース

100000
100000 99999 99998 ... 3 2 1
->166661666700000

贤珠制作の不満ランキングは10万要素のランキングで、比较が必要です...このテストケースでは,どの3つの要素を選択しても条件を満たすため,C(106,3)C(10^6,3)C(106,3)の結果と同じである.