526互联

P1253 扶苏的问题

发布时间 2023-08-29 09:46:57作者: 糖豆爸爸

\(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\)操作，因为有一部分区间可能不会被这样更新，

#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;
}