Hatena::Grouptopcoder

kuuso1の日記

2014-08-15

CodeForces Round261 D Pashmak and Parmida's problem

| 06:51 | CodeForces Round261 D Pashmak and Parmida's problem - kuuso1の日記 を含むブックマーク はてなブックマーク - CodeForces Round261 D Pashmak and Parmida's problem - kuuso1の日記

http://codeforces.com/contest/459/problem/D

  • 数列 Ai (i=1 to n) が与えられる。
  • 関数 f(l, r, x) を l ≤ k ≤ rであって Ak = x となるkの個数と定義する。
  • f(1, i, Ai) > f(j, n, Aj)となる(i, j)のペアの数を求める。

(制約)1 ≤ n ≤ 10^6, 1 ≤ Ai ≤ 10^9

まず、f(1, i, Ai)とf(j, n, Aj)を具体的に求める。Dictinaryで値の出現頻度を昇順・降順でなめて計算すればよい。

各iに対して、f(1, i, Ai) > f(j, n, Aj)となる個数を求めたいが、そのままだとO(n*n)でTLEする。

ここで、i=n-2から見ていくことを考えると、すでにみた結果を順次足していけばよいことがわかる。

f:id:kuuso1:20140816064458p:image

BITを使って、各値の登場頻度数を更新しながら足し上げていくことで答えが得られる。計算量オーダーはO(nlogn)。

using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		int N=ri();
		int[] A=ria();
		
		int[] ac=new int[N];
		int[] dc=new int[N];
		
		//各値の頻度を計算
		Dictionary<int,int> D=new Dictionary<int,int>();
		for(int i=0;i<N;i++){
			if(!D.ContainsKey(A[i]))D.Add(A[i],0);
			D[A[i]]++;
			ac[i]=D[A[i]];
		}
		D.Clear();
		for(int i=N-1;i>=0;i--){
			if(!D.ContainsKey(A[i]))D.Add(A[i],0);
			D[A[i]]++;
			dc[i]=D[A[i]];
		}
		
		long cnt=0;
		BIT BB=new BIT(N+2);
		for(int i=N-2;i>=0;i--){
			BB.Add(dc[i+1],1);
			cnt+=BB.Sum(ac[i]-1);
		}
		Console.WriteLine(cnt);
		
	}
	
		
	public Sol(){
	}
	class BIT{
		int MM;
		int n;
		long[] bit;
		public BIT(int n_){
			n=n_;
			MM=1<<18;
			while(MM<n*4)MM<<=1;
			bit=new long[MM+1];
		}
		public void Add(int i,long x){
			while(i<=n){
				bit[i]+=x;
				i+=(i&-i);
			}
		}
		public long Sum(int i){
			long s=0;
			while(i>0){
				s+=bit[i];
				i-= (i&-i);
			}
			return s;
		}
	}	

}		

BIT初使用だったので。本番は無駄にバグらせて撃沈。。