TopCoder SRM 839 : Div1 Medium LimitedSwaps

ちょっと手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=17861

問題

整数列Wが与えられる。
このうち隣接する2要素は、和がL以下であればswap可能とする。
Wの転倒数を最小化し、その値を求めよ。

解法

i番目の要素W[i]に対し、W[j]＞W[i]かつj＞iであるj番目の要素を、i番目の要素の後ろに持っていけない条件を考える。
W[k]＞L-W[i]となるi未満で最大のkを考えると、j≦kがその条件となる。

W[i]の小さい順にiを処理しよう。
その際、BITを用いて未処理のインデックスiの総和を高速に求められるようにする。
「W[k]＞L-W[i]となるi未満で最大のk」はRange Minimum Queryで二分探索すれば求められる。
あとはj≦kかつW[j]＞W[i]であるjの個数は、BITで数えることができる。

ll W[252525];

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,19> bit;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	// static V const def=1LL<<60; min
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v; //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<18> st;

class LimitedSwaps {
	public:
	long long minInversions(int N, int L, int M, vector <int> Wprefix, int seed) {
		ll state = seed;
		int i;
		vector<ll> Ws;
		FOR(i,Wprefix.size()) W[i]=Wprefix[i];
		for(i=Wprefix.size();i<N;i++) {
			state = (state * 1103515245 + 12345)%(1LL<<31);
			W[i]=1+state%M;
		}
		ZERO(bit.bit);
		
		vector<pair<int,int>> V;
		FOR(i,N) {
			V.push_back({W[i],i});
			bit.add(i,1);
			st.update(i,W[i]);
		}
		sort(ALL(V));
		ll ret=0;
		int j;
		FORR(v,V) {
			i=v.second;
			int t=i;
			for(j=20;j>=0;j--) if(t-(1<<j)>=0) {
				int w=st.getval(t-(1<<j),i);
				if(w+W[i]<=L) t-=1<<j;
			}
			ret+=bit(t-1);
			bit.add(i,-1);
			
		}
		return ret;
		
	}
}

まとめ

これはswapできない条件の考察ができれば、あとはもうすぐ。