PCK2012本選「イヅア辞書」

AOJ0271
想定解よりも良い解が見つかったので
O(RNlogN)
このlogNはかなり小さいのでほぼ無視してよい。

探索により解を見つける場合、可能性はN!通りあるので現実的ではない。
が、同じ文字が複数出現しないことを利用すると計算により位置を求めることができる。
具体的にはN分岐の木構造をイメージすると分かりやすい。
深さDがD文字目の分岐に相当すると考える事で1文字目から順番に計算することで解を導くことが出来る。
また、想定解はBITを用いてO(NlogN)だがBITの代わりにstd:vectorを使うことでO(N^2logN)が達成できる。
vector.erase()のオーダーが重くTLEになってしまうこの解法ですが、RがNに比べ極端に小さい事を利用した座標圧縮を行うことができます。
値が連続する部分をD文字分一まとめに処理(計算)することでこれが実現できる。
最悪のケースを考えてもRは50、つまり圧縮すれば本来のNの部分が１つRに置き換わるのでO(RNlogN)が達成出来る。

実際にこの解法はAOJにおいて最大ケースでも0.11msとかなりの高スコアが出せるのでstd:vectorの応用性の高さに感動できる良い問題だと思いました。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>

using namespace std;

#define FOR(I,N) for(int I = 0; I < (int)(N); I++)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)
#define MOD (1000000007)
#define ll long long

int d,n;
vector<int> sorted;
ll rui[100001];
int array[100001];

int main(){
	int i,j;
	int r,a,b;
	rui[0] = 1;
	FOR(i,100001){
		if(i!=0){
			rui[i] = (rui[i-1]*i)%MOD;
		}
	}
	while(cin>>n,n){
		cin>>r;
		sorted.clear();
		FOR(i,n){
			array[i] = i;
			sorted.pb(i);
		}
		sort(sorted.begin(),sorted.end());
		FOR(i,r){
			cin>>a>>b;a--;b--;
			swap(array[a], array[b]);
		}
		ll ans = 0;
		FOR(i,n-1){
			vector<int>::iterator index = lower_bound(sorted.begin(),sorted.end(),array[i]);
			vector<int>::iterator aft = index;
			ans+= (index-sorted.begin())*rui[n-i-1];
			ans%=MOD;
			int count = 0;
			for(j = i+1;j<n-1;j++){///いくつ連続してるか
				if(array[j]!=array[j-1]+1)break;
				count++;
				ans+= (index-sorted.begin())*rui[n-i-1-count];
				ans%=MOD;
			}
			i = j-1;
			aft+=count+1;
			sorted.erase(index,aft+1);
		}
		cout<<ans<<endl;
	}
	return 0;
}