Codeforces #174 Div1 D. Tourists

方針はすぐ立ったけど、割と実装が面倒な問題。
http://codeforces.com/contest/286/problem/D

問題

2次元座標で(-1,0)、(1,0)にいる2人が、ある時点からY座標正方向に速度1で移動する。
ここで、M個の壁がある。各壁は時刻T[i]に瞬間的に(0,L[i])-(0,R[i])を結ぶ線分上に登場する。
移動中の2人を結んだ線分上に、登場済みの壁が存在する場合、2人は互いの姿を見られない。

ここでN個のクエリがあり、各クエリは2人の移動開始時刻Q[i]で与えられる。
各クエリに対し、2人が互いの姿を確認できない時間を答えよ。

解法

姿を見える見えないと考えると一見ややこしいが、要は時刻(Q[i]+p)の時点でY座標(0,p)に壁があるような時間の和を求める問題である。

まず壁のY座標を圧縮した配列PP[i]を作成し各区間(0,PP[i])-(0,PP[i+1])に壁ができる最速の時間CT[i]を求める。
ここで出発時刻をtとすると、この区間は以下のように確認できない時間に影響する。

• t ≦ CT[i]-PP[i+1]なら、この区間は壁ができる前に通過するので、確認できない時間は0。
• t ≧ CT[i]-PP[i]なら、この区間に踏み込んだ時点ですでに壁ができているので、区間通過中(PP[i+1]-PP[i])の時間だけ確認できない。
• その間、CT[i]-PP[i+1] ＜ t ＜ CT[i]-PP[i]なら、区間通過中に壁ができ、確認できない時間はt-(CT[i]-PP[i+1])とtの一次関数となる。

各クエリについて、各区間ごとに上記値を加算すればよい。
このままだとO(NM)かかるので、先にクエリをソートしておく。
後はtの係数成分と定数成分でimos法を用いれば計算量を落とすことができる。

座標圧縮がO(M*logM)、imos法のための成分指定がO(M*logN)、クエリのソートがO(N*logN)。
NとMの上限はほぼ同じなので、大体O(M*logM)で済む。

int N,M;
ll L[100020],R[100020],T[100020];
ll Q[100020];
vector<pair<ll,ll> > QP;
ll PP[200200];
ll AS[200200],BS[200200],ret[200200];
vector<ll> S[200200],E[200200];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>L[i]>>R[i]>>T[i];
	FOR(i,N) cin>>Q[i], QP.push_back(make_pair(Q[i],i));
	sort(QP.begin(),QP.end());
	
	// compress
	map<ll,ll> UM;
	UM[0]=0;
	FOR(i,M) UM[L[i]]=UM[R[i]]=1;
	i=0;
	ITR(it,UM) it->second=i++, PP[it->second]=it->first;
	FOR(i,M) S[UM[L[i]]].push_back(T[i]),E[UM[R[i]]].push_back(T[i]);
	
	map<ll,int> CS;
	FOR(i,UM.size()) {
		FOR(j,E[i].size()) if(--CS[E[i][j]]==0) CS.erase(E[i][j]);
		FOR(j,S[i].size()) CS[S[i][j]]++;
		if(CS.size()) {
			ll ct=CS.begin()->first;
			x=lower_bound(QP.begin(),QP.end(),make_pair(ct-PP[i+1],0LL))-QP.begin();
			y=lower_bound(QP.begin(),QP.end(),make_pair(ct-PP[i],0LL))-QP.begin();
			AS[x]++; AS[y]--;
			BS[x]-=ct-PP[i+1], BS[y]+=ct-PP[i];
		}
	}
	
	ll aa=0,bb=0;
	FOR(i,N) aa+=AS[i], bb+=BS[i], ret[QP[i].second]=aa*QP[i].first+bb;
	FOR(i,N) cout<<ret[i]<<endl;
}

まとめ

これはすんなり方針が立って良かった。
tの係数成分のimos法が自力で書けたしね。