扶苏的问题
题目描述
给定一个长度为 n n n 的序列 a a a,要求支持如下三个操作:
- 给定区间 [ l , r ] [l, r] [l,r],将区间内每个数都修改为 x x x。
- 给定区间 [ l , r ] [l, r] [l,r],将区间内每个数都加上 x x x。
- 给定区间 [ l , r ] [l, r] [l,r],求区间内的最大值。
输入格式
第一行是两个整数,依次表示序列的长度 n n n 和操作的个数 q q q。
第二行有 n n n 个整数,第 i i i 个整数表示序列中的第 i i i 个数 a i a_i ai。
接下来 q q q 行,每行表示一个操作。每行首先有一个整数 o p op op,表示操作的类型。
- 若 o p = 1 op = 1 op=1,则接下来有三个整数 l , r , x l, r, x l,r,x,表示将区间 [ l , r ] [l, r] [l,r] 内的每个数都修改为 x x x。
- 若 o p = 2 op = 2 op=2,则接下来有三个整数 l , r , x l, r, x l,r,x,表示将区间 [ l , r ] [l, r] [l,r] 内的每个数都加上 x x x。
- 若 o p = 3 op = 3 op=3,则接下来有两个整数 l , r l, r l,r,表示查询区间 [ l , r ] [l, r] [l,r] 内的最大值。
输出格式
对于每个 o p = 3 op = 3 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 % 10\% 10% 的数据, n = q = 1 n = q = 1 n=q=1。
- 对于 40 % 40\% 40% 的数据, n , q ≤ 1 0 3 n, q \leq 10^3 n,q≤103。
- 对于 50 % 50\% 50% 的数据, 0 ≤ a i , x ≤ 1 0 4 0 \leq a_i, x \leq 10^4 0≤ai,x≤104。
- 对于 60 % 60\% 60% 的数据, o p ≠ 1 op \neq 1 op=1。
- 对于 90 % 90\% 90% 的数据, n , q ≤ 1 0 5 n, q \leq 10^5 n,q≤105。
- 对于 100 % 100\% 100% 的数据, 1 ≤ n , q ≤ 1 0 6 1 \leq n, q \leq 10^6 1≤n,q≤106, 1 ≤ l , r ≤ n 1 \leq l, r \leq n 1≤l,r≤n, o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\} op∈{1,2,3}, ∣ a i ∣ , ∣ x ∣ ≤ 1 0 9 |a_i|, |x| \leq 10^9 ∣ai∣,∣x∣≤109。
提示
请注意大量数据读入对程序效率造成的影响。
思路
线段树上维护三个值: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; // 更新赋值标记mdy
tr[p].add = 0; // 一旦存在赋值,先前的增加全部失效
}
void lazy_add(int p, i64 k) // 更新p结点add的懒标记
{
tr[p].w += k;
if (tr[p].mdy != LLONG_MAX) // 如果存在赋值标记,则在赋值标记上增加k
tr[p].mdy += k;
else // 否则在add标记上增加k
tr[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;
}