Codeforces 484(#276 Div1) E. Sign on Fence

Codeforces データ構造 二分探索

問題

長方形の板がN枚並んで出来ているフェンスがある。
i番目の板は幅1, 高さがh[i]の長方形で、下側の辺は地面にぴったりとくっついている。


このフェンスに看板を貼る候補がQ通りある。
各候補は、l, r, wで表され、l枚目からr枚目の板の内部に幅wの長方形の看板を貼りたいことを意味する。
看板は、底の面が地面にぴったりくっつくように、板からはみ出ないよう貼らなければならない。


それぞれの候補に対して貼れる看板の最大の高さを求めよ。

制約条件

N≦10^5
h[i]≦10^9
Q≦10^5

方針

二分探索 + 永続Segment Tree + 連続する1の個数。
貼る看板の高さがhだとする。


このとき、h以上の高さの板のみが使える。
a[i]をa[i] = h[i] ≧ h ? 1 : 0という配列だとすると、貼れる最大の幅は、
[l, r]の区間でa[i]の連続する1の個数の最大値に等しい。


区間に対して連続する1の個数を高速に求めるクエリを処理するには、
segment木に、

  • 自分の区間での1の連続する個数
  • 自分の区間の一番右から連続する1の個数
  • 自分の区間の一番左から連続する1の個数

を持たせればよい。


任意のhに対してこのクエリを答えたいので、セグメント木を永続化すればよい。


という解法は思いついていたんだけど、まさかそんな面倒そうな方針が想定解じゃないだろうなーと思ってeditorial見たら想定解だったらしい。

ソースコード

const int MX = 2000000;
int ch[MX][2], dat[MX], datL[MX], datR[MX], root[MX], sz = 1;

inline int add(int rt, int l, int r, int idx){
	if(l + 1 == r){
		dat[sz] = datL[sz] = datR[sz] = 1;
		return sz++;
	}
	int m = (l + r) >> 1;
	if(idx < m){
		int tmp = add(ch[rt][0], l, m, idx);
		dat[sz] = max(dat[rt], max(dat[ch[sz][0] = tmp], dat[ch[sz][1] = ch[rt][1]]));
	}
	else{
		int tmp = add(ch[rt][1], m, r, idx);
		dat[sz] = max(dat[rt], max(dat[ch[sz][0] = ch[rt][0]], dat[ch[sz][1] = tmp]));
	}
	dat[sz] = max(dat[sz], datR[ch[sz][0]] + datL[ch[sz][1]]);
	datL[sz] = max(datL[rt], datL[ch[sz][0]] + (datL[ch[sz][0]] == (m - l) ? datL[ch[sz][1]] : 0));
	datR[sz] = max(datR[rt], datR[ch[sz][1]] + (datR[ch[sz][1]] == (r - m) ? datR[ch[sz][0]] : 0));
	
	return sz++;
}
inline int query(int rt, int a, int b, int l, int r){
	if(b <= l || a >= r) return 0;
	if(a <= l && r <= b) return dat[rt];
	
	int m = (l + r) / 2;
	
	if(b <= m) return query(ch[rt][0], a, b, l, m);
	if(a >= m) return query(ch[rt][1], a, b, m, r);
	
	int res = max(query(ch[rt][0], a, b, l, m), query(ch[rt][1], a, b, m, r));
	
	if(a <= m && m < b) res = max(res, min(m - a, datR[ch[rt][0]]) + min(b - m, datL[ch[rt][1]]));
	return res;
}

const int N = 131072;
int n, h[N];
vi idx[N];

int main(){
	vi hs;
	scanf("%d", &n);
	rep(i, n) scanf("%d", h + i), hs.pb(h[i]);
	
	sort(all(hs)); hs.erase(unique(all(hs)), hs.end());
	rep(i, n){
		h[i] = lower_bound(all(hs), h[i]) - hs.begin();
		idx[h[i]].pb(i);
	}
	
	int M = hs.size();
	rep(i, M){
		int k = M - 1 - i;
		root[i + 1] = root[i];
		rep(j, idx[k].size()) root[i + 1] = add(root[i + 1], 0, N, idx[k][j]);
	}
	
	int q; scanf("%d", &q);
	while(q--){
		
		int l, r, w; scanf("%d%d%d", &l, &r, &w); l--;
		int lo = 0, hi = M, mid;
		while(lo + 1 < hi){
			mid = (lo + hi) / 2;
			int k = M - 1 - mid;
			if(query(root[k + 1], l, r, 0, N) >= w) lo = mid;
			else hi = mid;
		}
		printf("%d\n", hs[lo]);
	}
	
	return 0;
}