GMOJ5673 爬山法 题解

Solution

显然先想到处理出每个点能看到的最高的顶点。

然后考虑模拟题目的过程，一段一段走时间复杂度显然不够优秀。

考虑我们要求什么，我们需要求出\(u\)到\(v\)的最近的一个点，使得这个点能看到的点比\(v\)能看到的点更高。

然后这个东西可以直接线段树，当然也可以二分+st表

复杂度\(O(n\log n)\)

Code

#include <cstdio>

#include <iostream>

#define LL long long

#define RE register

#define IN inline

using namespace std;

IN int read() {

	int res = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar());

	for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);

	return res;

}

int n, le[2000010], ri[2000010], nxt[2000010], st[2000010][20], lg[2000010];

LL f[2000010];

struct Point {

	int x, y;

}p[2000010];

inline double slope(int x, int y) {return 1.0 * (p[x].y - p[y].y) / (p[x].x - p[y].x);}

inline bool cmp(int x, int y) {

	if(x == y) return false;

	if(p[x].y > p[y].y) return true;

	if(p[x].y == p[y].y) return p[x].x > p[y].x;

	return false;

}

int stk[2000010];

inline int pmax(int x, int y) {return cmp(x, y) ? x : y;}

void preWork() {

	int top = 0;

	for(int i = 1; i <= n; ++i) {

		while(top > 1 && slope(stk[top], i) >= slope(stk[top], stk[top - 1])) -- top;

		if(top) le[i] = stk[top]; stk[++top] = i;

	}

	top = 0;

	for(int i = n; i; --i) {

		while(top > 1 && slope(stk[top], i) <= slope(stk[top], stk[top - 1])) -- top;

		if(top) ri[i] = stk[top]; stk[++top] = i;

	}

	for(int i = 1; i <= n; ++i) {

		nxt[i] = pmax(le[i], ri[i]);

		if(cmp(i, nxt[i])) nxt[i] = 0;

		st[i][0] = nxt[i];

	}

	for(int i = 1; i <= lg[n]; ++i)

		for(int j = 1; j <= n; ++j)

			st[j][i] = pmax(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);

	return ;

}

inline LL abs(int x) {return x < 0 ? -x : x;}

inline int query(int l, int r) {int len = r - l + 1; return pmax(st[l][lg[len]], st[r - (1 << lg[len]) + 1][lg[len]]);}

LL solve(int k) {

	if(f[k] || !nxt[k]) return f[k];

	int res = nxt[k];

	if(nxt[k] < k) {

		for(int l = nxt[k], r = k - 1, mid; l <= r;) {

			mid = l + r >> 1;

			if(cmp(query(mid, k), nxt[k])) res = mid, l = mid + 1;

			else r = mid - 1;

		}

	}

	else {

		for(int l = k + 1, r = nxt[k], mid; l <= r;) {

			mid = l + r >> 1;

			if(cmp(query(k, mid), nxt[k])) res = mid, r = mid - 1;

			else l = mid + 1;

		}

	}

	f[k] = solve(res) + abs(res - k);

	return f[k];

}

void out(int x) {printf("%d %d\n",p[x].x,p[x].y);}

int main() {

	freopen("mountain.in","r",stdin);

	freopen("mountain.out","w",stdout);

	n = read();

	for(int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;

	for(int i = 1; i <= n; ++i) p[i].x = read(), p[i].y = read();

	preWork();

	for(int i = 1; i <= n; ++i) solve(i);

	for(int i = 1; i <= n; ++i) printf("%lld\n",f[i]);

	return 0;

}```

GMOJ5673 爬山法 题解的相关教程结束。