洛谷 P1253 扶苏的问题 题解 线段树

扶苏的问题

题目描述

给定一个长度为 $n$ 的序列 $a$，要求支持如下三个操作：

1. 给定区间 $[l,r]$，将区间内每个数都修改为 $x$。
2. 给定区间 $[l,r]$，将区间内每个数都加上 $x$。
3. 给定区间 $[l,r]$，求区间内的最大值。

输入格式

第一行是两个整数，依次表示序列的长度 $n$ 和操作的个数 $q$。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列中的第 $i$ 个数 $a_i$。
接下来 $q$ 行，每行表示一个操作。每行首先有一个整数 $op$，表示操作的类型。

• 若 $op=1$，则接下来有三个整数 $l,r,x$，表示将区间 $[l,r]$ 内的每个数都修改为 $x$。
• 若 $op=2$，则接下来有三个整数 $l,r,x$，表示将区间 $[l,r]$ 内的每个数都加上 $x$。
• 若 $op=3$，则接下来有两个整数 $l,r$，表示查询区间 $[l,r]$ 内的最大值。

输出格式

对于每个 $op=3$ 的操作，输出一行一个整数表示答案。

样例 #1

样例输入 #1

6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6

样例输出 #1

7
6
-1

样例 #2

样例输入 #2

4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4

样例输出 #2

0

数据规模与约定

• 对于 $10\%$ 的数据，$n=q=1$。
• 对于 $40\%$ 的数据，$n,q\le 10^3$。
• 对于 $50\%$ 的数据，$0\le a_i,x\le 10^4$。
• 对于 $60\%$ 的数据，$op\ne 1$。
• 对于 $90\%$ 的数据，$n,q\le 10^5$。
• 对于 $100\%$ 的数据，$1\le n,q\le 10^6$，$1\le l,r\le n$， o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\} op∈{1,2,3}，$|a_i|,|x|\le 10^9$。

提示

请注意大量数据读入对程序效率造成的影响。

思路

线段树上维护三个值：w，add，mdy。它们分别为区间最值，加数的懒标记，赋值的懒标记。当赋值懒标记存在时，加数标记改为在赋值标记 mdy 的值上加数；否则在加数懒标记 add 的值上加数。这样，在下传懒标记的时候，我们只需判断是下传 mdy 懒标记，还是下传 add 懒标记，还是不下传懒标记。因为在上述的打标记操作下，懒标记 mdy 和懒标记 add 不可能同时存在。此外，本题需注意数据范围：类型记得开long long int，读入数据的效率需优化。

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef long long ll;#define lc (p << 1)
#define rc (p << 1 | 1)const int maxn = 1e6 + 6;
i64 a[maxn];struct node
{int l, r;i64 w, add, mdy; // 懒标记add和mdy
} tr[maxn * 4];void pushup(int p)
{tr[p].w = max(tr[lc].w, tr[rc].w); // w维护区间最大值
}void lazy_mdy(int p, i64 k) // 更新p结点mdy的懒标记
{tr[p].w = k;tr[p].mdy = k; // 更新赋值标记mdytr[p].add = 0; // 一旦存在赋值，先前的增加全部失效
}void lazy_add(int p, i64 k) // 更新p结点add的懒标记
{tr[p].w += k;if (tr[p].mdy != LLONG_MAX) // 如果存在赋值标记，则在赋值标记上增加ktr[p].mdy += k;else // 否则在add标记上增加ktr[p].add += k;
}void pushdown(int p) // 下传懒标记
{if (tr[p].mdy != LLONG_MAX){lazy_mdy(lc, tr[p].mdy);lazy_mdy(rc, tr[p].mdy);tr[p].mdy = LLONG_MAX;}else if (tr[p].add != 0){lazy_add(lc, tr[p].add);lazy_add(rc, tr[p].add);tr[p].add = 0;}
}// 建树
void build(int p, int l, int r) // p是当前位置，l和r表示区间
{if (l == r){tr[p] = {l, r, a[l], 0, LLONG_MAX};return;}int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);tr[p] = {l, r, max(tr[lc].w, tr[rc].w), 0, LLONG_MAX};
}// 区间修改
void modify(int p, int x, int y, i64 k)
{if (x <= tr[p].l && tr[p].r <= y){lazy_mdy(p, k);return;}int mid = tr[p].l + tr[p].r >> 1;pushdown(p);if (x <= mid)modify(lc, x, y, k);if (y > mid)modify(rc, x, y, k);pushup(p);
}// 区间增加
void update(int p, int x, int y, i64 k)
{if (x <= tr[p].l && tr[p].r <= y){lazy_add(p, k);return;}int mid = tr[p].l + tr[p].r >> 1;pushdown(p);if (x <= mid)update(lc, x, y, k);if (y > mid)update(rc, x, y, k);pushup(p);
}// 区间询问最大值
i64 query(int p, int x, int y) // p是当前位置，x和y表示区间
{if (x <= tr[p].l && tr[p].r <= y) // 已覆盖则返回该部分的结果return tr[p].w;int mid = tr[p].l + tr[p].r >> 1;pushdown(p);i64 ans = LLONG_MIN;if (x <= mid)ans = max(ans, query(lc, x, y));if (y > mid)ans = max(ans, query(rc, x, y));return ans;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);int n, q;cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];}build(1, 1, n);while (q--){int op;cin >> op;if (op == 1){int l, r;i64 x;cin >> l >> r >> x;modify(1, l, r, x);}else if (op == 2){int l, r;i64 x;cin >> l >> r >> x;update(1, l, r, x);}else{int l, r;cin >> l >> r;cout << query(1, l, r) << '\n';}}return 0;
}