yukicoder : No.1568 Sushi

割と実装が大変。
https://yukicoder.me/problems/no/1568

問題

長さLの回転ずし屋を考える。
寿司レーンは速さ1で初期状態で時計回りに回っている。
その後、時刻A[i]で回転方向が反転する、という情報がN個与えられる。

この状態で以下の各クエリに答えよ。

• 時刻Tに、客が来店し座標Xに着席した。時刻T以降の任意のタイミングに座標0に寿司を置けるとき、座標Xに寿司が到達する最速の時刻を求めよ。

解法

問題を言い換える。
まず以下を定める。
f(x) := 時刻0に座標0に置いた寿司が、時刻xにどの座標にあるか。なお、レーンがループ状であることを無視し、L以上や負の値も取れるようにする。

T以上の時刻tに対し、以下のいずれかを満たす最小のuを求める問題となる。

• f(u)-f(t)=X
• f(u)-f(t)=L-X

そこで、SegTreeを作る。SegTreeの最小のノードは、回転方向が一致する時間の区間に相当する。
そして、ノード毎にf(x)の最小値・最大値及び、最大値から最小値への落差の最大値と、最小値から最大値への上昇分の最大値を持とう。
このSegTree上を二分探索することで、「最大値から最小値への落差の最大値」がX以上になるuや「最小値から最大値への上昇分の最大値」がL-X以上になるuを求めて行こう。

ll L;
int N,Q;
ll A[1<<19];
ll X[1<<19];
ll D;

struct node {
	ll dif;
	ll ma,mi,up,down;
};

node merge(node a,node b) {
	node v;
	if(a.ma==0&&a.mi==0) return b;
	if(b.ma==0&&b.mi==0) return a;
	v.dif=a.dif+b.dif;
	v.ma=max(a.ma,a.dif+b.ma);
	v.mi=min(a.mi,a.dif+b.mi);
	v.up=max({a.up,b.up,b.ma+a.dif-a.mi});
	v.down=min({a.down,b.down,b.mi+a.dif-a.ma});
	return v;
}

node V[20][1<<19];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>N>>Q;
	A[0]=0;
	FOR(i,N) {
		cin>>A[i+1];
	}
	for(i=N+1;i<1<<18+1;i++) A[i]=1LL<<53;
	for(i=1;i<1<<18;i++) {
		if(i%2==1) X[i]=X[i-1]+A[i]-A[i-1];
		else X[i]=X[i-1]-(A[i]-A[i-1]);
	}
	N+=2;
	FOR(i,N-1) {
		node& v=V[0][i];
		v.dif=X[i+1]-X[i];
		if(X[i+1]>X[i]) {
			v.dif=v.ma=v.up=X[i+1]-X[i];
			v.mi=v.down=0;
		}
		else {
			v.dif=v.mi=v.down=X[i+1]-X[i];
			v.ma=v.up=0;
		}
	}
	FOR(i,19) FOR(j,N) V[i+1][j]=merge(V[i][j],V[i][j+(1<<i)]);
	
	while(Q--) {
		ll B,C;
		cin>>B>>C;
		B=(B+D)%L;
		C=(C+D)%1000000000000000LL;
		
		x=lower_bound(A,A+N,C+1)-A-1;
		ll dif;
		if(X[x]<X[x+1]) {
			dif=A[x+1]-C;
		}
		else {
			dif=-(A[x+1]-C);
		}
		
		if(dif>=B) {
			D=B;
		}
		else if(dif<=B-L) {
			D=abs(B-L);
		}
		else {
			node v;
			v.dif=dif;
			v.ma=v.up=max(0LL,v.dif);
			v.mi=v.down=min(0LL,v.dif);
			x++;
			for(i=18;i>=0;i--) {
				node v2=merge(v,V[i][x]);
				if(v2.up<B&&v2.down>B-L) {
					x+=1<<i;
					v=v2;
				}
			}
			if(X[x]<X[x+1]) {
				D=A[x]+(B-(v.dif-v.mi))-C;
			}
			else {
				D=A[x]+(-(v.ma-v.dif)-(B-L))-C;
			}
		}
		
		
		cout<<D<<endl;
		
	}
}

まとめ

レーンの長さが最大10^15なので、最長で寿司が届くのは3000万年以上かかるようです。