Good Bye 2014, C : New Year Book Reading

問題文

　http://codeforces.com/contest/500/problem/C

問題概要

　今，手元に 冊の本があり， 番の本の重さは である．部屋には本棚が無いので，本は縦に積まれている．ある本を読むときの手順は以下のようになる．

1. 読みたい本の上にある本を全て持ち上げる
2. 読みたい本を抜き取とる
3. 持ち上げた本をそのまま下ろす
4. 読み終わった本を上に乗せる

　これから 日に渡って 1 冊ずつ本を読む．読みたいと思っている本の情報は配列 によって与えられ， 日目に読みたい本は である．
　初期状態での本の詰み方を任意に選べるとき，手順 1. で持ちあげなければならない本の重みの操作の最小値はいくらか？

解法

　題意より，一度以上読まれた本の位置は確定しています．逆に，一度も読まれていない本の位置は自由に動かせます（都合のよい場所にあったことにできる）．ある本を読むとき，過去にその本を読んだとき以降に読まれた本は全て持ち上げなければなりません．そうでない本のうち，今読もうとしている本を前回読んだとき以前に読んだ本は読もうとしている本より下に積まれているはずなので持ち上げる必要はありません（というより，持ち上げたくても持ち上げることはできません）．それ以外の，すなわち，一度も読まれていない本は，今読もうとしている本のすぐ下にでもあったことにすればいいので，持ち上げる必要はありません．
　このような場合分けの元，各本が最後に読まれた日付を管理しつつ答えを計算することで問題を解くことができます．また，このような戦略を実行できる初期状態での本の順序は， に初めて出現する位置が早いものを上に置く積み方なので，この積み方を最初に作ってからシミュレーションすることによって同じ答えを得ることができます．実際，この 2 つの方法は，本の順序を陽にもつか否かは違いますが本質的に同じことをしています．

コード

using LL = long long;
using VI = vector< int >;
template < typename T = int > using VT = vector<T>;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define PB push_back

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int N, M;
	cin >> N >> M;

	VI W( N ), B( M );
	cin >> W >> B;

	transform( ALL( B ), B.begin(), bind( minus< int >(), _1, 1 ) );

	VI order;
	{
		VT< bool > used( N );
		FOR( b, B )
		{
			if ( !used[b] )
			{
				order.PB( b );
				used[b] = true;
			}
		}
	}

	LL res = 0;
	FOR( b, B )
	{
		const int p = find( ALL( order ), b ) - order.begin();
		REP( i, 0, p )
		{
			res += W[ order[i] ];
		}
		for ( int i = p; 0 < i; --i )
		{
			swap( order[ i - 1 ], order[i] );
		}
	}

	cout << res << endl;

	return 0;
}