Codeforces ECR #029 : E. Turn Off The TV

また問題を読み間違える…。
http://codeforces.com/contest/863/problem/E

問題

1次元の数直線における区間がN個与えられる。
このうち1個取り除いても、「どの区間にも覆われない整数座標の数」が減らないような区間があれば、それを求めよ。

解法

まず区間を座標圧縮しておく。
後は区間に定数を加算することと、RMQができるSegTreeを持っておけばよい。

各区間に対しSegTreeで1を加算しよう。
再度各区間を探索し、その区間が常に２個以上の区間で覆われる、すなわち区間の最小値が2以上であれば、その区間が解。

int N;
int L[202020],R[202020];
vector<int> V;

static ll const def=-1<<20;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, mi;
	SegTree_3(){
		val.resize(NV*2,0); mi.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 1<<30;
		if(x<=l && r<=y) return mi[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			mi[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			mi[k]=val[k]+min(mi[k*2],mi[k*2+1]);
		}
	}
};
SegTree_3<int,1<<20> st;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		R[i]++;
		V.push_back(L[i]);
		V.push_back(R[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	FOR(i,N) {
		L[i]=lower_bound(ALL(V),L[i])-V.begin();
		R[i]=lower_bound(ALL(V),R[i])-V.begin();
		st.update(L[i],R[i],1);
	}
	
	FOR(i,N) if(st.getval(L[i],R[i])>1) return _P("%d\n",i+1);
	_P("-1\n");
}

まとめ

何だこの問題…とは思うけどEducationalだしいいのかな。