[Gym-102020J] Joseph and Tests （线段树+二分）

https://vjudge.net/problem/Gym-102020J

将前后房子的差值作为线段树底部节点
查询时要二分查询出最远距离

int a[maxn], t[maxn];
int maxx[maxn * 4];

void build(int rt, int l, int r) {
	if (l == r) {
		maxx[rt] = t[l];
		return;
	}
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	maxx[rt] = max(maxx[rt << 1], maxx[rt << 1 | 1]);
}

void change(int rt, int l, int r, int pl, int pr) {
	if (l == r) {
		maxx[rt] = t[l];
		return;
	}
	int mid = l + r >> 1;

	if (pl <= mid)	change(rt << 1, l, mid, pl, pr);
	if (pr > mid)	change(rt << 1 | 1, mid + 1, r, pl, pr);
	maxx[rt] = max(maxx[rt << 1], maxx[rt << 1 | 1]);
}

ll query(int rt, int l, int r, int pl, int pr) {
	ll res = 0;
	if (pl <= l && pr >= r)	return maxx[rt];
	int mid = l + r >> 1;
	if (pl <= mid)	res = max(res, query(rt << 1, l, mid, pl, pr));
	if (pr > mid)	res = max(res, query(rt << 1 | 1, mid + 1, r, pl, pr));
	return res;
}

signed main() {
	int n; n = rd();
	for (int i = 0; i < n; ++i) {
		a[i] = rd();
		if (i)	t[i] = abs(a[i] - a[i - 1]);
	}
	if (n == 1) {
		int q; q = rd();
		for (int i = 0; i < q; ++i) {
			int op, a, b;
			op = rd(); a = rd(); b = rd();
			if (op == 2)	puts("1");
		}
		return 0;
	}
	build(1, 1, n - 1);
	int q; q = rd();
	for (int i = 0; i < q; ++i) {
		int op, x, y;
		op = rd(); x = rd(); y = rd();
		if (op == 1) {
			a[x - 1] = y;
			if (x != n)	t[x] = abs(a[x] - a[x - 1]);
			if (x != 1)	t[x - 1] = abs(a[x - 1] - a[x - 2]);
			if (x == 1)	change(1, 1, n - 1, x, x);
			else if (x == n)	change(1, 1, n - 1, x - 1, x - 1);
			else change(1, 1, n - 1, x - 1, x);
		}
		else {
			int l = x, r = n - 1;
			ll res = n;
			while (l <= r) {
				int mid = l + r >> 1;
				ll tmp = query(1, 1, n - 1, x, mid);
				if (tmp <= y)	l = mid + 1;
				else res = mid, r = mid - 1;
			}
			printf("%lld\n", res);
		}
	}
	return 0;
}

[Gym-102020J] Joseph and Tests （线段树+二分）

原文：https://www.cnblogs.com/wanshe-li/p/14492624.html