Codeforces #261 Div2 D. Pashmak and Parmida's problem

こちらも割とすんなり。
http://codeforces.com/contest/459/problem/D

問題

N要素の数列A[i]が与えられる。
関数f(l,r,x)とは、A[l]～A[r]のうちxの個数を返す。

ここでf(1,i,A[i]) > f(j,N,A[j])となる(i,j)の対(ただしi

解法

まずf(1,i,A[i])及びf(j,N,A[j])を各i,jについて求める。
A[i]の上限が大きいが、Nが10^6以下なのでmapを使って同じ数値の登場回数を計算すればよい。

あとはiをN→1と小さくしていくループをこなしつつ、BITを使ってf(1,i,A[i])より小さなf(j,N,A[j])の数をカウントしていけばよい。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int entry) {
		V s=0;
		entry++;
		while(entry>0) s+=bit[entry-1], entry -= entry & -entry;
		return s;
	}
	void update(int entry, V val) {
		entry++;
		while(entry <= (1<<ME)) bit[entry-1] += val, entry += entry & -entry;
	}
};
BIT<int,20> bt;
int N,A[1000010];
int N1[1000010],N2[1000010];
map<int,int> M1,M2;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N) N1[i]=++M1[A[i]];
	FOR(i,N) N2[N-1-i]=++M2[A[N-1-i]];
	
	ll ret=0;
	FOR(i,N) {
		j=N-1-i;
		ret+=bt.total(N1[j]-1);
		bt.update(N2[j],1);
	}
	cout << ret << endl;
	
}

まとめ

本番はmapじゃなく無駄に座標圧縮＋BITでfの値を求めてしまった…。