Codeforces #524 Div2 F. Katya and Segments Sets

問題設定が無駄に長いな…。
https://codeforces.com/contest/1080/problem/F

問題

N個の1次元区間の集合S[i]が与えられる。
この状態で以下のクエリに順次答えよ。なお、クエリ回答順を変更することはできない。

集合の範囲A,Bと区間[X,Y]が与えられる。
S[A...B]のすべてが[X,Y]に含まれる区間を1つ以上持つか判定せよ。

解法

平方分割で解く。
その前に、まず単一の集合S[i]において高速に判定する方法を考えよう。
S[i]に属する区間[L,R]を、(L,R)のペア順に並べ替える。
さらにその上で、ペアの2項めのRについて、自身の位置より後ろにもっと小さい値があるならそれに置き換えよう。
そうするとS[i]に属する[L,R]の並びは、1項め2項めともに昇順になる。
クエリ[X,Y]が与えられた場合、X≦LとなるS[i]中最小の[L,R]を求め、R≦Yなら条件を満たす。

平方分割においても同様である。
一連のS[i]の区間[L,R]を(L,R)順にソートし、各Lに対し、バケット内における各S[i]のRの最小値の最大値を求めよう。
これは尺取り法の要領でdequeやmultisetを使い行うことができる。

int N,M,K;
const int DI=350;
vector<pair<int,int>> V[101010];
vector<vector<int>> V2[350];
int st[101010];

int check(int v,int L,int R) {
	int a=lower_bound(ALL(V[v]),make_pair(L,0))-V[v].begin();
	if(a==V[v].size()) return 0;
	return V[v][a].second<=R;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,K) {
		cin>>x>>y>>k;
		k--;
		V[k].push_back({x,y});
	}
	int cur=0;
	FOR(i,N) if(V[i].size()) {
		sort(ALL(V[i]));
		for(j=V[i].size()-2;j>=0;j--) V[i][j].second=min(V[i][j].second,V[i][j+1].second);
		FORR(v,V[i]) V2[i/DI].push_back({v.first,v.second,i%DI});
	}
	FOR(i,DI) if(V2[i].size()) {
		sort(ALL(V2[i]));
		deque<int> DQ[DI];
		multiset<int> M;
		
		for(int L=0,R=0;L<V2[i].size();L++) {
			while(R<V2[i].size() && M.size()<DI) {
				auto v=V2[i][R++];
				DQ[v[2]].push_back(v[1]);
				if(DQ[v[2]].size()==1) M.insert(v[1]);
			}
			if(M.size()<DI) V[N+i].push_back({V2[i][L][0],1<<30});
			else V[N+i].push_back({V2[i][L][0],*M.rbegin()});
			
			x=V2[i][L][2];
			M.erase(M.find(DQ[x].front()));
			DQ[x].pop_front();
			if(DQ[x].size()) M.insert(DQ[x].front());
		}
	}
	while(M--) {
		int A,B,L,R;
		cin>>A>>B>>L>>R;
		A--;
		int ok=1;
		while(ok==1 && A<B && A%DI) ok&=check(A++,L,R);
		while(ok==1 && A<B && B%DI) ok&=check(--B,L,R);
		while(ok==1 && A<B) ok&=check(N+A/DI,L,R), A+=DI;
		
		if(ok) cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
}

まとめ

最初「S[i]中1個でも条件を満たすものがあるか」という問題を解いてしまいタイムロスした。