Codeforces #271 Div2 E. Pillars

実装に手間取りはしたけど、解法自体は割とすんなり思いついた。
http://codeforces.com/contest/474/problem/E

問題

N個の柱が１列に並んでおり、その高さはH[i]である。
この柱のうち幾つかをindex昇順で選択し、柱の間を移動したい。
その際、選択した隣同士の柱の高さの差の絶対値はD以上でなければならない。

最大何個の柱を選択できるか。
また、どの柱を選択すればよいか。

解法

まず柱の高さを座標圧縮する。
その上で、indexの小さい順にDPする。
その際、各高さに対応して最大何個の柱を選択できるかSegmentTreeで管理する。
また、その柱選択数最大値と合わせて、その時の柱番号を管理する。

高さの差がD以上の条件があるので、H[i]についてDPする場合は、H[i]-D以下とH[i]+D以上の２つの範囲においてSegTreeを検索すればよい。

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

int N,D;
ll H[100500];
map<ll,int> M;
vector<ll> K;
int ma[100500],cur[100500],pre[100500];

SegTree_1<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	M[0]=M[1LL<<30]=0;
	FOR(i,N) cin>>H[i], M[H[i]]++;
	i=0;
	ITR(it,M) it->second=i++, K.push_back(it->first);
	
	FOR(i,N) {
		j=M[H[i]];
		cur[i]=1;
		pre[i]=-1;
		// upper
		k=lower_bound(K.begin(),K.end(),H[i]+D)-K.begin();
		pair<ll,int> v=st.getval(k,1<<18);
		if(cur[i]<v.first+1) cur[i]=v.first+1, pre[i]=v.second;
		
		// lower
		k=upper_bound(K.begin(),K.end(),max(0LL,H[i]-D))-K.begin();
		v=st.getval(0,k);
		if(cur[i]<v.first+1) cur[i]=v.first+1, pre[i]=v.second;
		
		if(cur[i]>ma[j]) ma[j]=cur[i], st.update(j,ma[j],i);
	}
	
	x=max_element(cur,cur+N)-cur;
	_P("%d\n",cur[x]);
	vector<int> V;
	while(x>=0) V.push_back(x+1), x=pre[x];
	
	FOR(i,V.size()) _P("%d ",V[V.size()-1-i]);
	_P("\n");
}

まとめ

２値を管理するSegTreeライブラリを持ってなかったので、本番時間を食った。