//
// accumulative map
//   basically a map<K,V>, but it eliminates duplication lazily
//   first keep all inserted elements in a vector. only when the buffer
//   overflows, it eliminates duplication
//

template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)>
struct amap
{
	typedef typename vector< pair<K,V> >::iterator iterator;
	struct ByKey { bool operator()(const pair<K,V>& a, const pair<K,V>& b) const { return a.first<b.first; } };

	vector< pair<K,V> > kv;
	amap() { kv.reserve(LIMIT); }

	void add(const K& k, const V& v)
	{
		kv.push_back( make_pair(k,v) );
		if( kv.size() == LIMIT )
			normalize();
	}

	iterator begin()       { return kv.begin(); }
	iterator end()         { return kv.end(); }
	void swap( amap& rhs ) { kv.swap(rhs.kv); }

	// Tested: SRM 469 Lv3 (Accumulate)
	void normalize()
	{
		sort(kv.begin(), kv.end(), ByKey());
		int i=0;
		for(int j=0; j<kv.size(); ++i)
		{
			int k = j;
			kv[i] = kv[k];
			while( ++j<kv.size() && kv[k].first==kv[j].first )
				kv[i].second += kv[j].second;
		}
		kv.resize(i);
	}
/*
	// Not Tested (Prefer First)
	void normalize()
	{
		sort(kv.begin(), kv.end(), ByKey());
		int i=0;
		for(int j=0; j<kv.size(); ++i)
		{
			int k = j;
			kv[i] = kv[k];
			while( ++j<kv.size() && kv[k].first==kv[j].first )
				{}
		}
		kv.resize(i);
	}

	// Not Tested (Prefer Last)
	void normalize()
	{
		sort(kv.begin(), kv.end(), ByKey());
		int i=0;
		for(int j=0; j<kv.size(); ++i)
		{
			int k = j;
			while( ++j<kv.size() && kv[k].first==kv[j].first )
				{}
			kv[i] = kv[j-1];
		}
		kv.resize(i);
	}
*/
};
