kmjp's blog

競技プログラミング参加記です

LeetCode Biweekly Contest 131 : 3161. Block Placement Queries

唐突に難易度8が2連続来たな。
https://leetcode.com/problems/block-placement-queries/description/

問題

1次元の数直線がある。
以下のクエリに順次答えよ。

  • 指定した座標xに障害物を置く。
  • 座標xとサイズszが与えられる。区間[0,x]の間で、間に障害物を挟まないようなsz以上の区間が取れるか判定せよ。

解法

以下の2つのデータ構造を使う。

  • 障害物のある座標のset
  • 障害物のある座標に対し、次の障害物までの距離を格納するSegTree。区間最大値を取れる。

前者のクエリのたびに上記2構造を更新し、後者のクエリではSegTreeを使ってsz以上の区間を取れるか判定しよう。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,0);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return 0;
		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<<18> st;

class Solution {
public:
    vector<bool> getResults(vector<vector<int>>& queries) {
		set<int> S={0,(1<<17)-1};
		st.update(0,(1<<17)-1);
		vector<bool> ret;
		FORR(q,queries) {
			int x=q[1];
			int y=*prev(S.lower_bound(x+1));
			int v=st.getval(y,y+1);
			if(q[0]==1) {
				st.update(y,x-y);
				st.update(x,v-(x-y));
				S.insert(x);
			}
			else {
				if(x-y>=q[2]) {
					ret.push_back(1);
				}
				else if(st.getval(0,y)>=q[2]) {
					ret.push_back(1);
				}
				else {
					ret.push_back(0);
				}
			}
		}
		
		FORR(q,queries) {
			st.update(q[1],0);
		}
		return ret;
        
    }
};

まとめ

なんかLeetCodeってSegTree使う問題を難易度高めに判定するよね。