|
|
## [$P1253$ 扶苏的问题](https://www.luogu.com.cn/problem/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
|
|
|
|
|
|
```
|
|
|
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
|
|
|
|
|
|
```
|
|
|
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 \leq 10^3$。
|
|
|
- 对于 $50\%$ 的数据，$0 \leq a_i, x \leq 10^4$。
|
|
|
- 对于 $60\%$ 的数据，$op \neq 1$。
|
|
|
- 对于 $90\%$ 的数据，$n, q \leq 10^5$。
|
|
|
- 对于 $100\%$ 的数据，$1 \leq n, q \leq 10^6$，$1 \leq l, r \leq n$，$op \in \{1, 2, 3\}$，$|a_i|, |x| \leq 10^9$。
|
|
|
|
|
|
#### 提示
|
|
|
|
|
|
请注意大量数据读入对程序效率造成的影响。
|
|
|
|
|
|
### 二、线段树解法
|
|
|
|
|
|
- 1.其实就是用线段树进行简单的区间修改（每个数修改为$v$， 每个数加$v$）和 区间查询。因为有两种区间修改，所以用$modify$和$add$两个懒标记；
|
|
|
|
|
|
- 2.两个操作之间的关系：每次一个区间若修改为$v$，那么区间的$add$就要清空为$0$。每次下传标记先下传区间的$modify$再下传$add$；
|
|
|
|
|
|
- 3.$pushup$维护区间最大值；
|
|
|
|
|
|
- 4.$modify$改变整个区间每个值为$v$之后还是得要下传$add$操作，因为有一部分区间可能不会被这样更新，
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1e6 + 10;
|
|
|
int n, m;
|
|
|
int a[N];
|
|
|
|
|
|
// 线段树模板
|
|
|
#define int long long
|
|
|
#define INF 0x3f3f3f3f
|
|
|
#define ls u << 1
|
|
|
#define rs u << 1 | 1
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int modify, add; // 两个懒标记：区间内统一修改为v,区间内统一加上v
|
|
|
int mx; // 区间最大值，结果
|
|
|
} tr[N << 2];
|
|
|
|
|
|
void pushup(int u) {
|
|
|
tr[u].mx = max(tr[ls].mx, tr[rs].mx);
|
|
|
}
|
|
|
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r; // 范围
|
|
|
|
|
|
tr[u].modify = INF; // 更新懒标记INF,更新懒标记INF
|
|
|
tr[u].add = 0; // 更新懒标记INF,加法懒标记0
|
|
|
/*
|
|
|
Q1:为什么modify的懒标记要设置为INF，而不是0呢？
|
|
|
答：因为如果设置为0，我们就不知道到底是想整体区间都修改为0，还是默认值！我们分不清！
|
|
|
同时，由于modify的值域是abs(x)=1e9,也就是可能是0，也可能是-1e9,所以，我们只能选择找一个范围外的数字做为初始值，
|
|
|
才能区分开是默认值，还是人为修改值。
|
|
|
|
|
|
Q2: 为什么add懒标记可以设置为初始化是0呢？
|
|
|
答：因为对于加法而言，加零还是不加零是没有区别的，所以，人为区间加，是不会加零的。
|
|
|
|
|
|
Q: 为什么这个对于懒标记的初始化，是在build这个递归函数的入口处就进行呢的？而对于叶子节点的赋值是在l==r的判断里？
|
|
|
答：我们需要头脑中有线段树的整体架构，在每个统计区间(也可以理解为每个统计点),都是有两个懒标记：整体修改标记modify
|
|
|
和整体加法标记add的,懒标记可不是作用到叶子上的，而是作用在统计节点上的！所以，对于每个需要分裂的区间，当然都需要对
|
|
|
懒标记进行赋值了。
|
|
|
*/
|
|
|
|
|
|
if (l == r) {
|
|
|
tr[u].mx = a[l]; // 单节点时，区间最大值,准备通过pushup函数，向上汇总统计信息
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
int mid = (l + r) >> 1;
|
|
|
build(ls, l, mid);
|
|
|
build(rs, mid + 1, r);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
void pushdown(int u) {
|
|
|
// 注意:要先处理统一修改的modify懒标记，再处理add标记!
|
|
|
|
|
|
if (tr[u].modify != INF) { // 如果存在modify的懒标记
|
|
|
tr[ls].modify = tr[rs].modify = tr[u].modify; // 向左右儿子传递统一修改的懒标记
|
|
|
tr[ls].mx = tr[rs].mx = tr[u].modify; // 统一修改后，都是一样的值，那么左右儿子的最大值当然也是这个值
|
|
|
tr[ls].add = tr[rs].add = 0; // 本来想向下传递加法的懒标记，这样好了，不用传递了，因为新来的要求把整体都修改成modify了
|
|
|
tr[u].modify = INF; // modify懒标记都传递下去，处理完了，设置为默认值吧
|
|
|
}
|
|
|
|
|
|
if (tr[u].add) { // 如果存在add的懒标记
|
|
|
tr[ls].add += tr[u].add; // 左儿子的add懒标记加上新的增加出来的add
|
|
|
tr[rs].add += tr[u].add; // 右儿子的add懒标记加上新的增加出来的add
|
|
|
tr[ls].mx += tr[u].add; // 左儿子的最大值加上add
|
|
|
tr[rs].mx += tr[u].add; // 右儿子的最大值加上add
|
|
|
tr[u].add = 0; // add懒标记传递完毕
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void modify(int u, int l, int r, int v) {
|
|
|
if (l <= tr[u].l && r >= tr[u].r) { // 完全覆盖
|
|
|
tr[u].mx = v; // 区间所有值修改为v,当然最大值也是v
|
|
|
tr[u].modify = v; // 全部修改为v,懒标记修改为v, 不向下继续传递
|
|
|
tr[u].add = 0; // 整体都修改为v了，以前不管有啥add懒标记，其实都没用了，因为人家要统一修改为v
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
pushdown(u); // 懒标记下传时，不一定是一个懒标记，所以，不要在这里通过if进行判断决定是否进行pushdown,而是在pushdown内部完成懒标记的判定
|
|
|
|
|
|
// 找交集
|
|
|
|
|
|
// 方法1
|
|
|
if (l <= tr[ls].r) modify(ls, l, r, v); // 左儿子的右大于等于l,表示左儿子与修改区间有交集
|
|
|
if (r >= tr[rs].l) modify(rs, l, r, v); // 右儿子的左小于等于r,表示右儿子与修改区间有交集
|
|
|
|
|
|
// 方法2
|
|
|
// int mid = (tr[u].l + tr[u].r) >> 1;
|
|
|
// if (l <= mid) modify(ls, l, r, v);
|
|
|
// if (r > mid) modify(rs, l, r, v);
|
|
|
|
|
|
// 修改完毕，需要向上汇总统计信息
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
void add(int u, int l, int r, int v) { // 加v
|
|
|
if (l <= tr[u].l && r >= tr[u].r) { // 完全覆盖
|
|
|
tr[u].mx += v; // 每个人都+v,最大值肯定也要+v
|
|
|
tr[u].add += v; // 修改整体的加法懒标记
|
|
|
// Q:为什么不修改modify懒标记呢？
|
|
|
// 答：当add执行时，需要把前面的都整明白后再进行add。那么，如果原来有modify的动作，就先modify,再add, 否则计算就不正确了
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
pushdown(u);
|
|
|
// 找交集
|
|
|
|
|
|
// 方法1
|
|
|
if (l <= tr[ls].r) add(ls, l, r, v); // 左儿子的右大于等于l,表示左儿子与修改区间有交集
|
|
|
if (r >= tr[rs].l) add(rs, l, r, v); // 右儿子的左小于等于r,表示右儿子与修改区间有交集
|
|
|
|
|
|
// 方法2
|
|
|
// int mid = (tr[u].l + tr[u].r) >> 1;
|
|
|
// if (l <= mid) add(ls, l, r, v);
|
|
|
// if (r > mid) add(rs, l, r, v);
|
|
|
|
|
|
// 修改完毕，需要向上汇总统计信息
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
int query(int u, int l, int r) {
|
|
|
if (l <= tr[u].l && r >= tr[u].r) return tr[u].mx;
|
|
|
|
|
|
pushdown(u);
|
|
|
|
|
|
// 方法1
|
|
|
if (r < tr[rs].l) return query(ls, l, r);
|
|
|
if (l > tr[ls].r) return query(rs, l, r);
|
|
|
return max(query(ls, l, r), query(rs, l, r));
|
|
|
|
|
|
// 方法2
|
|
|
// int mid = (tr[u].l + tr[u].r) >> 1;
|
|
|
// int res = -1e16;
|
|
|
// if (l <= mid) res = max(res, query(ls, l, r));
|
|
|
// if (r > mid) res = max(res, query(rs, l, r));
|
|
|
// return res;
|
|
|
}
|
|
|
/*
|
|
|
答案：
|
|
|
7
|
|
|
6
|
|
|
-1
|
|
|
*/
|
|
|
signed main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("P1253.in", "r", stdin);
|
|
|
#endif
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
cin >> n >> m;
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
|
|
build(1, 1, n);
|
|
|
|
|
|
while (m--) {
|
|
|
int op;
|
|
|
int l, r, x;
|
|
|
cin >> op;
|
|
|
if (op == 1) {
|
|
|
cin >> l >> r >> x;
|
|
|
modify(1, l, r, x);
|
|
|
} else if (op == 2) {
|
|
|
cin >> l >> r >> x;
|
|
|
add(1, l, r, x);
|
|
|
} else {
|
|
|
cin >> l >> r;
|
|
|
printf("%lld\n", query(1, l, r));
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
### 三、柯朵莉树解法（非正解）
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 1e6 + 10;
|
|
|
#define int long long // 不开LONG LONG见祖宗
|
|
|
int n, m;
|
|
|
|
|
|
// TLE 掉最后的两个测试点
|
|
|
// 柯朵莉树模板
|
|
|
// 不要采用构建函数与{}混搭的使用，WA的让你怀疑人生！
|
|
|
// 以后记住：在声明结构体时，不要使用构造函数!!
|
|
|
struct Node {
|
|
|
int l, r; // l和r表示这一段的起点和终点
|
|
|
mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
|
|
|
bool operator<(const Node &b) const {
|
|
|
return l < b.l; // 规定按照每段的左端点排序
|
|
|
}
|
|
|
};
|
|
|
set<Node> s; // 柯朵莉树的区间集合
|
|
|
|
|
|
// 分裂:[l,x-1],[x,r]
|
|
|
set<Node>::iterator split(int x) {
|
|
|
auto it = s.lower_bound({x});
|
|
|
if (it != s.end() && it->l == x) return it; // 一击命中
|
|
|
it--; // 没有找到就减1个继续找
|
|
|
if (it->r < x) return s.end(); // 真的没找到,返回s.end()
|
|
|
|
|
|
int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
|
|
|
s.erase(it); // 删除整个区间
|
|
|
s.insert({l, x - 1, v}); //[l,x-1]拆分
|
|
|
// insert函数返回pair，其中的first是新插入结点的迭代器
|
|
|
return s.insert({x, r, v}).first; //[x,r]拆分
|
|
|
}
|
|
|
|
|
|
// 区间加
|
|
|
void add(int l, int r, int v) {
|
|
|
// 必须先计算itr,后计算itl
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
for (auto it = L; it != R; it++) it->v += v;
|
|
|
}
|
|
|
// 区间赋值
|
|
|
void assign(int l, int r, int v) {
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
s.erase(L, R); // 删除旧区间
|
|
|
s.insert({l, r, v}); // 增加新区间
|
|
|
}
|
|
|
|
|
|
int query(int l, int r) {
|
|
|
int res = -LONG_LONG_MAX; // 这个最小值太BT了，需要写成这么小！
|
|
|
auto R = split(r + 1), L = split(l);
|
|
|
for (; L != R; L++) res = max(res, L->v);
|
|
|
return res;
|
|
|
}
|
|
|
/*
|
|
|
答案：
|
|
|
7
|
|
|
6
|
|
|
-1
|
|
|
*/
|
|
|
signed main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("P1253.in", "r", stdin);
|
|
|
#endif
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
// 柯朵莉初始化
|
|
|
cin >> n >> m;
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
int x;
|
|
|
cin >> x;
|
|
|
s.insert({i, i, x}); // ① 需要初始化多个独立的区间
|
|
|
}
|
|
|
|
|
|
while (m--) {
|
|
|
int op;
|
|
|
int l, r, x;
|
|
|
cin >> op;
|
|
|
cin >> l >> r;
|
|
|
if (op == 1) {
|
|
|
cin >> x;
|
|
|
assign(l, r, x); // ②平推
|
|
|
} else if (op == 2) {
|
|
|
cin >> x;
|
|
|
add(l, r, x); // ③区间内都加上x
|
|
|
} else
|
|
|
printf("%lld\n", query(l, r)); // ④查询
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
