Codeforces Round 489 (Div. 2) E. Nastya and King-Shamans（线段树）

本文主要是介绍Codeforces Round 489 (Div. 2) E. Nastya and King-Shamans（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：E. Nastya and King-Shamans

---

题目大意：

---

给出一个长度为 $n$ 的非负整数数组 $a$，设 $s_i$ 为 $a$ 的前 $i$ 项前缀和：$s_i={\sum }_{i=1}^i{a}_i$ 。

给出 $q$ 次询问，格式为 $p$ $x$，表示将 $a_p$ 的值改为 $x$ 。

修改完成后，回答是否存在一个位置 $i$ ，使得 $a_i=s_{i-1}$ 。

如果有多个位置可以任意输出，否则输出 $-1$ 。

解题思路：

---

非常好线段树题。

注意到查询的是一个前缀和的形式，即 $a_i=s_{i-1}$ 的形式，这直接在线段树上是不好维护的，查询也不好查询。我们把 $a_i$ 和 $s_{i-1}$ 绑定在一起，变成 $a_i-s_{i-1}$ 的形式。

那么考虑一个单点修改造成的影响，假设初值为 $a_p$，修改后为 $a_p^{\prime }$ 。

• 修改后 $a_p>a_{p^{\prime }}$ ，那么我们后续的 $s_{p+1},s_{p+2},...,s_n$ 显然都会减少 $\mid a_p^{\prime }-a_p\mid$ 。
• 修改后 $a_p<a_{p^{\prime }}$ ，那么我们后续的 $s_{p+1},s_{p+2},...,s_n$ 显然都会增加 $\mid a_p^{\prime }-a_p\mid$ 。
• 对位置 $p$ 而言，直接修改 $a_p^{\prime }$ 和 $a_p$ 的差值即可。

这样，我们把单点修改变成了区间加的形式，就能动态维护 $a_i$ 和 $s_{i-1}$ 的关系了。

现在考虑怎么做查询的操作，我们容易发现一个事实：

如果要使得 $a_i=s_{i-1}$ 的话，那么我们 $s_i$ 会是成倍增长的。

比如考虑如下的情况：

$a:$ $[1,1,2,4,8,16,32,64,128,...]$
$s:$ $[1,2,4,8,16,32,64,128,256,...]$

又由于 $1\le a_i\le 10^9$ ，设 V = max ⁡ { a 1 , a 2 , . . . , a n } V=\max\{a_{1},a_{2},...,a_{n}\} V=max{a1​,a2​,...,an​} 那么我们最多只会有 $\log V$ 个 $a_i$ 会成为答案，因为 $s_i$ 最多经过 $\log V$ 次倍增之后就会大于 $10^9$ 的范围，因此我们可能成为答案的位置不会超过 $\log V$ 个。

想想我们不可能成为答案的位置会是什么样的，一定是 $a_i-s_{i-1}<0$ 。

而那些所有的 $a_i-s_{i-1}\ge 0$ 的值都可能会是我们的答案，且又因为 $a_i\ge s_{i-1}$，那么每次一定会使得 $s_i\ge 2\cdot s_{i-1}$ ，这些位置不会超过 $\log V$ 个。

线段树维护区间最大值，我们暴力递归每一个区间，如果区间最大值 $<0$ ，则我们直接跳过这些区间，我们只搜索那些 $[l,r]$ 区间的最大值 $\ge 0$ 的，当搜索到叶子节点时，且 $a_i-s_{i-1}=0$ 我们就找到了一个合法答案，这样单次询问的复杂度会是 $O(\log n\log V)$ 的，可以通过此题。

时间复杂度：$O(q\log n\log V)$

AC代码：

#include <bits/stdc++.h>
using namespace std;using PII = pair<int, int>;
using i64 = long long;const int N = 2e5 + 1;i64 Seg[N << 2], lzy[N << 2], a[N], pre[N];#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, rvoid build(int k, int l, int r) {if (l == r) {Seg[k] = a[l] - pre[l - 1];return;}int mid = l + r >> 1;build(lson), build(rson);Seg[k] = max(Seg[k << 1], Seg[k << 1 | 1]);
}void pushdown(int k, int l, int r) {int lt = k << 1, rt = k << 1 | 1;Seg[lt] += lzy[k], Seg[rt] += lzy[k];lzy[lt] += lzy[k], lzy[rt] += lzy[k];lzy[k] = 0;
}void Modify(int k, int l, int r, int x, int y, i64 v) {if (l >= x && r <= y) {Seg[k] += v;lzy[k] += v;return;}if (lzy[k]) pushdown(k, l, r);int mid = l + r >> 1;if (x <= mid) Modify(lson, x, y, v);if (y > mid) Modify(rson, x, y, v);Seg[k] = max(Seg[k << 1], Seg[k << 1 | 1]);
}int res = -1;
void Query(int k, int l, int r) {if (Seg[k] < 0 || res != -1) return;if (l == r) {if (Seg[k] == 0) {res = l;}return;}if (lzy[k]) pushdown(k, l, r);int mid = l + r >> 1;Query(lson), Query(rson);
}void solve() {int n, q;cin >> n >> q;for (int i = 1; i <= n; ++i) {cin >> a[i];pre[i] = pre[i - 1] + a[i];}build(1, 1, n);for (int i = 1; i <= q; ++i) {i64 p, v;cin >> p >> v;i64 add = v - a[p];a[p] = v;Modify(1, 1, n, p, p, add);if (p + 1 <= n) {Modify(1, 1, n, p + 1, n, -add);}res = -1;Query(1, 1, n);cout << res << '\n';}
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1; //cin >> t;while (t--) solve();return 0;
}

这篇关于Codeforces Round 489 (Div. 2) E. Nastya and King-Shamans（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---