IOI 2005-day1 Mountains

問題文 : 山の遊園地

問題概要 (問題文読みづらいので) :
長さ N の数列が与えられる. 次のクエリに答えよ.

• 区間 [l, r] の値を v に更新する. [I l r v]
• [1, x] の値がはじめてv を越えるようなx を求める. [Q v]

解法 :

遅延評価をするセグメント木を用いる. 次のような事ができればいい.

• 区間[0, x] のなかの部分和列の最大値を求める. 一般化して, 区間[l, r] の最大値を求める.
• 区間[0, x] の部分和を求める. 一般化して, 区間[l, r] の和を求める.
• 区間[l, r] を値 v に更新する.

更新は遅延評価の伝搬時にどうにかすれば良い. 残りの2 つは, 次のようにして更新すれば良い.

par.maxi = max(lch.maxi, rch.maxi, lch.right + rch.left);
par.sum = lch.sum + rch.sum;
par.left = max(lch.left, lch.sum + rch.left);
par.right = max(rch.right, rch.sum + lch.right);

これができれば, クエリを先読みして座標を圧縮すれば, 二分探索でQ のクエリにO(log^2 N) で答えられる.

ゆえに, 計算量はO(Qlog^2 N) となる. Q はクエリ数である.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

#define DEFAULT (10000000009ll)

using namespace std;

typedef long long lint;

vector<int> xs;
map<int, int> conv;

struct Node {
	lint sum, lazy;
	lint maxi, left, right;
	Node(){
		sum = maxi = left = right = 0, lazy = DEFAULT;
	}
} seg[1 << 20];

inline void eval(int k, int l, int r)
{
	if (seg[k].lazy != DEFAULT){
		seg[k].sum = seg[k].maxi = seg[k].left = seg[k].right = (lint)(xs[r] - xs[l]) * seg[k].lazy;
		
		if (k < (1 << 18) - 1){
			seg[k * 2 + 1].lazy = seg[k * 2 + 2].lazy = seg[k].lazy;
		}
		
		seg[k].lazy = DEFAULT;
	}
}

inline void _update(int k)
{
	seg[k].sum = seg[k * 2 + 1].sum + seg[k * 2 + 2].sum;
	seg[k].maxi = max(seg[k * 2 + 1].right + seg[k * 2 + 2].left, max(seg[k * 2 + 1].maxi, seg[k * 2 + 2].maxi));
	seg[k].left = max(seg[k * 2 + 1].sum + seg[k * 2 + 2].left, seg[k * 2 + 1].left);
	seg[k].right = max(seg[k * 2 + 2].sum + seg[k * 2 + 1].right, seg[k * 2 + 2].right);
}

void update(int a, int b, lint x, int k = 0, int l = 0, int r = xs.size())
{
	eval(k, l, r);
	
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		seg[k].lazy = x;
		eval(k, l, r);
		return;
	}
	
	update(a, b, x, k * 2 + 1, l, (l + r) / 2);
	update(a, b, x, k * 2 + 2, (l + r) / 2, r);
	_update(k);
}

Node null;

Node getMax(int a, int b, int k = 0, int l = 0, int r = xs.size())
{
	eval(k, l, r);
	
	if (b <= l || r <= a) return (null);
	
	if (a <= l && r <= b){
		return (seg[k]);
	}
	
	Node lch = getMax(a, b, k * 2 + 1, l, (l + r) / 2),
		 rch = getMax(a, b, k * 2 + 2, (l + r) / 2, r),
		 ret;
	ret.maxi = max(lch.right + rch.left, max(lch.maxi, rch.maxi));
	ret.sum = lch.sum + rch.sum;
	ret.left = max(lch.left, lch.sum + rch.left);
	ret.right = max(rch.right, rch.sum + lch.right);
	_update(k);
	return (ret);
}

char Qtype[100000];
int arg1[100000], arg2[100000], arg3[100000];

int main()
{
	null.left = null.right = null.maxi = -9999999999999ll;
	null.sum = 0;
	
	int n;
	
	scanf("%d", &n);
	
	
	int Q = 0;
	char q[32];
	while (scanf("%s", q) && q[0] != 'E'){
		if (q[0] == 'Q'){
			scanf("%d", arg1 + Q);
			Qtype[Q] = 'Q';
		}
		else {
			scanf("%d %d %d", arg1 + Q, arg2 + Q, arg3 + Q);
			xs.push_back(--arg1[Q]); xs.push_back(arg2[Q]);
			Qtype[Q] = 'I';
		}
		Q++;
	}
	
	xs.push_back(0); xs.push_back(n);
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	for (int i = 0; i < xs.size(); i++) conv[xs[i]] = i;
	
	for (int i = 0; i < Q; i++){
		if (Qtype[i] == 'Q'){
			int lo = 0, hi = xs.size() - 1;
			while (hi != lo){
				int mi = (hi + lo + 1) / 2;
				if (getMax(0, mi).maxi <= (lint)arg1[i]) lo = mi;
				else hi = mi - 1;
			}
			int mi = (hi + lo) >> 1;
			lint plus = (mi != xs.size() - 1 ? min((lint)(xs[mi + 1] - xs[mi]), (arg1[i] - getMax(0, mi).sum) / (getMax(mi, mi + 1).sum / (xs[mi + 1] - xs[mi]))) : 0);
			printf("%lld\n", (lint)xs[mi] + plus);
		}
		else {
			update(conv[arg1[i]], conv[arg2[i]], arg3[i]);
		}
	}
	
	return (0);
}