
牛客练习赛47 C DongDong跳一跳(线段树+思维)
发布日期:2021-05-08 15:15:36
浏览次数:25
分类:精选文章
本文共 1909 字,大约阅读时间需要 6 分钟。
问题分析与解决思路
在本题中,我们需要找到一个位置,使得在该位置停下时所能获得的鱼竿量最大。具体来说,对于每一个位置i,我们需要确定他停在该位置时所能覆盖的区间[a[i]-m, a[i]+m],并在此区间内找到最大值。为了高效地解决这个问题,我们可以使用线段树来维护区间内的最大值。
技术细节解释
构建线段树
线段树定义:
- 线段树是一个基于二叉树的数据结构,能够在O(log n)的时间复杂度内完成多个查询操作。
- 每个节点存储其对应区间内的最大值。
初始化线段树:
- 线段树的每个叶子节点对应一个位置,存储该位置的鱼竿量。
- 非叶子节点的值是其左右子节点中的最大值。
构建过程:
- 递归地将区间分割成两部分,直到区间长度为1时,叶子节点的值被确定。
- 非叶子节点的值通过比较左右子节点的值来确定。
查询操作
查询函数:
- 该函数负责查询某个区间[l, r]内的最大值。
- 通过递归地比较当前节点的区间是否与查询区间相交,进而决定需要查询哪些子节点。
查询过程:
- 如果当前节点的区间完全在查询区间内,则直接返回节点的最大值。
- 否则,递归查询左边和右边子节点,并取最大值。
更新操作
更新函数:
- 该函数用于更新某个位置的鱼竿量值。
- 根据位置的值,递归地更新对应的线段树节点。
更新过程:
- 如果当前节点的区间长度为1,则直接更新该节点的值。
- 否则,判断目标位置是否在左边或右边子节点中,并递归更新相应的子节点。
代码实现
#includeusing namespace std;const int maxn = 1e6 + 1000;typedef long long ll;struct cxk { int l, r; ll w;};tree[maxn << 1] cxk;int n, m, a[maxn], b[maxn];void build(int l, int r, int x) { cxk[x].l = l; cxk[x].r = r; if (l == r) { cxk[x].w = 0; return; } int mid = (l + r) >> 1; build(l, mid, x << 1); build(mid + 1, r, x << 1 | 1); cxk[x].w = max(cxk[x << 1].w, cxk[x << 1 | 1].w);}void update(int pos, ll v, int x) { if (cxk[x].l == cxk[x].r) { cxk[x].w = v; return; } int mid = (cxk[x].l + cxk[x].r) >> 1; if (pos <= mid) { update(pos, v, x << 1); } else { update(pos, v, x << 1 | 1); } cxk[x].w = max(cxk[x << 1].w, cxk[x << 1 | 1].w);}ll query(int l, int r, int x) { if (l > cxk[x].r || cxk[x].l > r) { return 0; } if (l <= cxk[x].l && cxk[x].r <= r) { return cxk[x].w; } int mid = (cxk[x].l + cxk[x].r) >> 1; ll ans = 0; if (l <= mid) { ans = max(ans, query(l, r, x << 1)); } if (mid + 1 <= r) { ans = max(ans, query(l, r, x << 1 | 1)); } return ans;}
代码解释
- 线段树结构:
cxk
结构用于存储线段树节点的区间信息和最大值。 - 构建函数:
build
函数负责初始化线段树,递归地将区间分割并更新最大值。 - 更新函数:
update
函数用于更新某个位置的值,递归地更新线段树。 - 查询函数:
query
函数用于查询区间内的最大值,递归地比较子节点区间并返回最大值。
通过上述方法,我们可以高效地找到每个位置停下的最大鱼竿量,从而解决问题。