TopCoder SRM 810 : Div1 Medium IcelandRingRoad

見たことあったので解法はすぐ思いついたけど、実装に手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=17083&rd=18756

問題

N個の町が道路で円周状につながっている。
今、道路が雪で使用不可になっており、隣接する町をつなぐ道路について、それぞれ整備コストが与えられる。

ここで、どことどこの町が道路で接続されてなければならない、という条件がP個与えられる。
各条件を満たすよう道路を整備するとき、総整備コストの最小値を求めよ。

解法

Codeforcesで2・3回見たことある。
少なくとも1つの道路は未整備で良いはずなので、未整備を確定させる道路を走査していこう。

未整備と確定した道路がある場合、P個の条件を満たすためには、その未整備確定道路を通らないために通れるべき道路が確定する。
そこで、走査の過程で通る道路が変わった(反対周りにをすることになった)条件について、その変更差分を考慮しつつ、1個以上の条件でカバーされる道路の領域についてコストの総和を求めよう。

以下のコードでは、区間加算と区間最小値を求めるSegTreeを使い、新規に1個以上の条件でカバーされるようになった道路のコスト分の加算や、新規にカバー条件がなくなった道路のコスト分の減算を行っている。

ll C[1505050],L[505050],W[505050];
vector<int> ev[1010101];

static ll const def=1<<20;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val;
	vector<pair<V,int>> ma;
	void init(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2);
		FOR(i,NV) {
			val[i+NV]=0;
			ma[i+NV]={0,i};
		}
		for(i=NV-1;i>=1;i--) ma[i]=min(ma[2*i],ma[2*i+1]);
	};
	
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return {def,0};
		if(x<=l && r<=y) return ma[k];
		auto a=min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
		a.first+=val[k];
		return a;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k].first+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=min(ma[k*2],ma[k*2+1]);
			ma[k].first+=val[k];
		}
	}
};
SegTree_3<int,1<<20> st;

int N;
class IcelandRingRoad {
	ll cur;
	void add(int L,int R) {
		st.update(L,R,1);
		while(L<R) {
			auto p=st.getval(L,R);
			assert(p.first>0);
			if(p.first>1) break;
			cur+=C[p.second%N];
			L=p.second+1;
		}
	}
	void del(int L,int R) {
		auto p=st.getval(L,R);
		assert(p.first>0);
		st.update(L,R,-1);
		while(L<R) {
			auto p=st.getval(L,R);
			if(p.first>0) break;
			cur-=C[p.second%N];
			L=p.second+1;
		}
	}
	
	
	public:
	int solve(int N, int P, int M, long long state) {
		int i,j;
		::N=N;
		st.init();
		FOR(i,N) {
			state = (state * 1103515245 + 12345) % (1LL<<31);
			C[i] = 1 + ((state / 10)%M);
			C[i+N] = 1 + ((state / 10)%M);
			ev[i].clear();
			ev[i+N].clear();
		}
		cur=0;
		FOR(j,P) {
			state = (state * 1103515245 + 12345) % (1LL<<31);
		    L[j] = ((state / 10) % N);
			state = (state * 1103515245 + 12345) % (1LL<<31);
		    W[j] = ((state / 10) % N);
		    if(L[j]==W[j]) {
				j--,P--;
				continue;
			}
			if(L[j]>W[j]) swap(L[j],W[j]);
			ev[L[j]].push_back(j);
			add(L[j],W[j]);
		}
		ll mi=cur;
		FOR(i,N) {
			mi=min(mi,cur);
			FORR(e,ev[i]) {
				del(L[e],W[e]);
				L[e]+=N;
				swap(L[e],W[e]);
				add(L[e],W[e]);
				ev[L[e]].push_back(e);
			}
			mi=min(mi,cur);
		}
		
		return mi;
	}
}

まとめ

Chalできそうなコードあったのに、入力形式が乱数ベースなので狙って落とせなかった。