Codeforces #284 Div1 D. Traffic Jams in the Land

これDの割にあまり難しくない。本番解けばよかったかな…。
http://codeforces.com/contest/498/problem/D

問題

1～(N+1)番の町が順に並んでおり、i番と(i+1)番の町の間はi番目の道路で結ばれている。
各道路は時間1で移動できる。
ただし、各道路は時間A[i]ごとに渋滞が発生しており、出発時刻がA[i]の倍数の時は移動できない。

ここで以下のクエリQ個に答えよ。

1. 町(x,y)間の最短移動距離を答える。
2. x番目の道路の渋滞パラメータをA[x]=yに変更する。

解法

A[i]は2～6の何れかである。
よって、道路全体の渋滞状態は最大で時刻60周期で変わる。
そのため移動開始時刻のmod 60の値ごとに、町の間の移動時間を求められるSegTreeを作ればよい。

SegTreeで区間の移動時間を求めるときに２つの小区間の時間の合計を求めるが、前半の小区間の時間によって、後半の小区間の(移動開始時刻%60)の値が変化する点に注意。

const int NV=1<<17;
int V[NV*2][60];
int N,Q;

int getval(int x,int y,int mo=0,int l=0,int r=NV,int k=1) {
	if(r<=x || y<=l) return 0;
	if(x<=l && r<=y) return V[k][mo];
	int a=getval(x,y,mo,l,(l+r)/2,k*2);
	int b=getval(x,y,(mo+a)%60,(l+r)/2,r,k*2+1);
	return a+b;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>r;
		FOR(j,60) V[NV+i+1][j]=1+((j%r)==0);
	}
	for(i=NV-1;i>=0;i--) {
		FOR(j,60) V[i][j]=V[i*2][j]+V[i*2+1][(j+V[i*2][j])%60];
	}
	
	cin>>Q;
	while(Q--) {
		cin>>s>>x>>y;
		if(s[0]=='A') {
			cout<<getval(x,y)<<endl;
		}
		else {
			r=NV+x;
			FOR(j,60) V[r][j]=1+((j%y)==0);
			while(r>1) {
				r>>=1;
				FOR(j,60) V[r][j]=V[r*2][j]+V[r*2+1][(j+V[r*2][j])%60];
			}
		}
	}
}

まとめ

本番は問題も見なかったけど、見たらすぐmod60が思いついた…。