Codeforces #292 Div1 C. Drazil and Park

これはきっちり解けて良かった。
http://codeforces.com/contest/516/problem/C

問題

N本の木が円周状に並んでおり、隣接する木の間の距離d[i]及び木の高さH[i]が与えられる。

ここでM個のクエリが与えられる。
各クエリでは、使用できない木の範囲(A[i],B[i])が与えられる。
これらの木および木の間を移動せず、異なる２本の木を選択したとき、２本の木x,yを登り降りしつつ間を移動する総距離(2(H[x]+H[y])+D(x,y))の最大値を答えよ。(D(x,y)は２本の木の距離)

解法

円周状問題の典型として、まず(N-1)番の木と0番の木の間の処理を楽にするため、全体を２倍に複製して2N個の木と考える。

使用できる範囲がp～q番の木とする。
２つのSegTreeを使って処理する。
各SegTreeはi番目の木に対し、１つ目は2*H[i]+D(i,2N-1)、２つ目は2*H[i]+D(0,i)を保持する。
p～qの間で両Segtreeで最大値となる木の番号がそれぞれx,yとすると、両方の値の合計は2(H[x]+H[y]) + D(x,2N-1) + D(y,0)となる。
そのためここからD(0,2N-1)を引けば2(H[x]+H[y]) + D(x,y)が求まる。

例外として、x==yの時がある(1本だけすごく高い木があるとか)。
その場合、１つ目の木および２つ目の木からxを除いたp～(x-1)及び(x+1)～qの間で２本目の木を求めればよい。

int N,M;
ll D[202000],H[202000];
ll DS[201000];

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=0;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return max(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i]=make_pair(def,NV+i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[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 make_pair(def,NV);
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int A[101000],B[101000];
int AD=1<<22;
SegTree_Pair<ll,1<<22> LT,RT;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>D[i], D[i+N]=D[i];
	FOR(i,N) cin>>H[i], H[i+N]=H[i];
	D[2*N-1]=0;
	FOR(i,200100) DS[i+1]=DS[i]+D[i];
	FOR(i,200100) LT.update(i,DS[200100]-DS[i]+2*H[i]);
	FOR(i,200100) RT.update(i,DS[i]+2*H[i]);
	
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(x<=y) A[i]=y+1, B[i]=N+x-1;
		else A[i]=y+1,B[i]=x-1;
		
		pair<ll,int> lc,rc,a1,a2;
		lc=LT.getval(A[i],B[i]+1);
		rc=RT.getval(A[i],B[i]+1);
		
		ll ret;
		if(lc.second!=rc.second) {
			ret = lc.first+rc.first-DS[200100];
		}
		else {
			ll ret1,ret2;
			a1=RT.getval(A[i],lc.second-AD);
			a2=RT.getval(lc.second-AD+1,B[i]+1);
			
			ret1 = lc.first + max(a1.first,a2.first);
			
			a1=LT.getval(A[i],lc.second-AD);
			a2=LT.getval(lc.second-AD+1,B[i]+1);
			ret2 = rc.first + max(a1.first,a2.first);
			
			ret=max(ret1,ret2)-DS[200100];
		}
		cout<<ret<<endl;
	}
	
}

まとめ

x==yの時の処理が若干トリッキーだが、なんとか本番に解けて良かった。
とはいえ、運動したいなら同じ木を２回登ってもいいじゃんね。