UTPC 2014 : J - 看板の塗り替え

割と実装がめんどい。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_j

問題

初期状態でN個の看板が1次元の数直線上に並んでいる。
各看板の位置はX[i]、色はA[i]である。

ここでQ個のクエリが与えられる。
各クエリは、以下の何れかである。

• Y[i]の位置にあるQ[i]の色の看板を撤去する
• Y[i]の位置にQ[i]の色の看板を追加する

各クエリの実行後の状態について、全ての看板を同色にするコストを求めよ。
なお、コストは下記の和である。

• 塗り手は原点におり、数直線を1移動するのにコストが1かかる
• 看板の色を1変えるのにコストが1かかる(塗り手が看板の座標にいないと色は変えられない)

解法

まず座標は先に圧縮しておく。
コストを最小にするには、移動コストを減らすか彩色コストを減らすかどちらかである。
よって以下の3つのうちコストの最小値を求めれば良い。

• 全てを左端の看板の色にそろえる。(左端に行く必要がなくなり移動コストが減る)
• 全てを右端の看板の色にそろえる。(右端に行く必要がなくなり移動コストが減る)
• 全てを色値が中央の看板の色にそろえる。(彩色コストが減る)

移動コストは、(塗らない看板を除いて)原点から右端の看板に行って左端に戻るか、左端に行って右端に戻るかいずれかである。
それぞれ色値毎の最左・最右の座標の看板をset等で管理することで、「ある色とは異なる色のうち最も左/右の看板」を簡単に得られる。
彩色コストはBITを2個用い、各色の看板の数を管理するBIT(二分探索で中央の色を求めるのに使う)と、色値の総和を管理するBIT(彩色コストの総和を求めるのに使う)で使い分けると良い。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};

int N,Q,NB;
BIT<ll,20> coln,cols;
int X[202000],A[202000],C[202000];
int rev[202000];

map<int,int> M;
vector<int> MV;
set<pair<int,int> > S;
set<pair<int,int> > Left, Right;
set<int> pos[200200];


ll dodo(int col) {
	
	if(Left.size()<=1) return 0;
	
	int LM=(Left.begin()->second!=col)?Left.begin()->first:(++Left.begin())->first;
	int RM=(Right.begin()->second!=col)?-Right.begin()->first:-(++Right.begin())->first;
	
	ll tn=coln.total(col-1);
	ll tot=cols.total(200001)-cols.total(col-1) - (S.size()-tn)*col;
	tot += tn*col-cols.total(col-1);
	
	return tot + (MV[RM]-MV[LM]) + min(abs(MV[RM]),abs(MV[LM]));
}

void change(int id, bool add) {
	set<int>& p = pos[A[id]];
	int x = M[X[id]];
	
	if(p.size()) {
		Left.erase(make_pair(*p.begin(),A[id]));
		Right.erase(make_pair(-*p.rbegin(),A[id]));
	}
	
	if(add) {
		S.insert(make_pair(x,id));
		rev[x] = id;
		coln.add(A[id],1);
		cols.add(A[id],A[id]);
		p.insert(x);
	}
	else {
		S.erase(make_pair(x,rev[x]));
		rev[x] = -1;
		coln.add(A[id],-1);
		cols.add(A[id],-A[id]);
		p.erase(x);
	}
	
	if(p.size()) {
		Left.insert(make_pair(*p.begin(),A[id]));
		Right.insert(make_pair(-*p.rbegin(),A[id]));
	}
}


void solve() {
	int i,j,k,l,r,x,y,q; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>A[i];
		M[X[i]]=0;
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>C[i+100000]>>X[i+100000]>>A[i+100000];
		M[X[i+100000]]=0;
	}
	M[1000000007]=M[-1000000007]=0;
	ITR(it,M) it->second = MV.size(), MV.push_back(it->first);
	
	FOR(i,N) change(i,true);
	
	for(q=100000;q<100000+Q;q++) {
		change(q,C[q]==1);
		
		ll mi=min(dodo(A[S.begin()->second]), dodo(A[S.rbegin()->second]));
		mi=min(mi,dodo(coln.lower_bound((S.size()+1)/2)));
		cout<<mi<<endl;
	}
}

まとめ

本番にさっくり書ける気がしないなぁ。