TopCoder SRM 845 : Div1 Medium LRSort

これは典型だな…。
https://community.topcoder.com/stat?c=problem_statement&pm=18001

問題

整数列Aと、クエリ列Tが与えられる。
各クエリは以下のいずれかを示す。

• A中の最小要素を、左隣りの要素とのswapを繰り返し、先頭に持ってきたうえで取り除く。
• A中の最大要素を、右隣りの要素とのswapを繰り返し、先頭に持ってきたうえで取り除く。

それぞれswap回数を求めよ。

解法

A中で残っている要素とその区間内の個数をsetとBITで管理すれば、各クエリのswap回数を高速に求められる。

int T[555555];
const ll mo=1000000007;
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

class LRSort {
	public:
	int simulate(int N, vector <int> Aprefix, int M, int seed, int B) {
		ll L=Aprefix.size();
		vector<ll> A;
		int i;
		FOR(i,L) A.push_back(Aprefix[i]);

		ll state = seed;
		for(i=L;i<N;i++) {
		    state = (state * 1103515245 + 12345)%(1LL<<31);
		    A.push_back(state%M);
		}

		ZERO(bt.bit);
		set<pair<int,int>> S;
		FOR(i,N) {
			bt.add(i,1);
			S.insert({A[i],i});
		}
		
		ll ret=0;
		ll p10=1;
		FOR(i,N-1) {
		    state = (state * 1103515245 + 12345)%(1LL<<31);
		    ll tmp=(state/(1<<20))%100;
		    if(tmp<B) {
				auto p=*S.rbegin();
				S.erase(p);
				int num=bt(N)-bt(p.second);
				ret+=num*p10%mo;
				bt.add(p.second,-1);
			}
			else {
				auto p=*S.begin();
				S.erase(p);
				int num=bt(p.second-1);
				ret+=num*p10%mo;
				bt.add(p.second,-1);
			}
			p10=p10*10%mo;
		}
		return ret%mo;
	}
}

まとめ

なんかTopCoderはN=10^5位のBITやSegTree乗せるだけ問題が高めのスコアで出る印象あるな…。
これCodeforcesだとDiv1B 750ptとかになりそう…。