Codeforces #468 Div1 C. Teodor is not a liar!

問題設定がややこしい。
http://codeforces.com/contest/930/problem/C

問題

１次元の数直線上において1～Mの1次元領域について、N個のセグメントが与えられる。
友人は1～Mのうちどこかに全セグメントに覆われた点があると信じている。
実際には1～Mのうちそうではない点が最低１個以上ある。
友人に各点を覆うセグメント数を聞かれたとき「全セグメントに覆われた点がある」ということが嘘であるとバレない最大質問数はいくつか。

解法

質問された各点を覆うセグメント数が山なりになっていれば嘘であるとばれない。
逆に、ある点を覆うセグメント数より多いセグメント数の点が左右に1個ずつ以上あると嘘だとばれる。

よってできるだけ多くの点が山なりになるようなケースを考えよう。
まず最初に各位置pを覆うセグメント数S(p)を累積和の要領で求める。
次に各頂点が山のピークになるケースを総当たりしよう。
ある頂点pがピークとなる場合、S(1)～S(p)のうちS(p)を含むLISと、逆順でS(M)～S(p)のうちS(p)を含むLISを連結すると、pを含む最長の山なりケースが求められる。

よって、数列を両方向からLISを求めていけばよい。

int N,M;
int S[101010];
int L[101010],R[101010];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		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]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> ML,MR;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		S[x]++;
		S[y+1]--;
	}
	for(i=1;i<=100000;i++) {
		S[i]+=S[i-1];
	}
	
	for(i=1;i<=M;i++) {
		L[i]=1+ML.getval(0,S[i]+1);
		ML.update(S[i],L[i]);
	}
	for(i=M;i>=1;i--) {
		R[i]=1+MR.getval(0,S[i]+1);
		MR.update(S[i],R[i]);
	}
	
	int ma=0;
	for(i=1;i<=M;i++) {
		ma=max(ma,L[i]+R[i]-1);
		cout<<i<<" "<<S[i]<<" "<<L[i]<<" "<<R[i]<<endl;
	}
	cout<<ma<<endl;
	
	
}

まとめ

Div1 Cにしては普段より簡単。