题目描述

难度分:$2100$

输入$n(1 \leq n \leq 10^5)$，$m(1 \leq m \leq 10^5)$。

一开始有一个长为$n$的数组$a$，所有$a[i]$都是$0$。下标从$1$开始。

然后输入$m$个操作，每个操作输入$l$，$r(1 \leq l \leq r \leq n)$，$x(-10^5 \leq x \leq 10^5)$，表示把$a$的下标$[l,r]$中的元素都增加$x$。

然后输入$q(1 \leq q \leq 10^5)$和$q$个询问，每个询问输入$k(1 \leq k \leq n)$，$s$，$t(1 \leq s \leq t \leq m)$。

对于每个询问，你需要选择$l$和$r$，满足$s \leq l \leq r \leq t$，然后执行第$l,l+1,…,r$个操作。输出最优操作后的$a[k]$的最大值。（每个询问互相独立）

输入样例$1$

2 6
1 1 -50
1 2 -20
2 2 -30
1 1 60
1 2 40
2 2 10
5
1 1 6
2 1 6
1 1 3
2 1 3
1 1 2

输出样例$1$

100
50
0
0
-20

输入样例$2$

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

输出样例$2$

3
3
4
3
0
-2

算法

扫描线

这个题比较容易想到的就是最大子段和，以操作编号作为索引建立线段树。那每个询问$(pos,l,r)$的答案其实就是原数组$a$在$pos$位置上，对应操作$[l,r]$的最大子段和，如果某个操作$(l,r,x)$的覆盖区间包括$pos$（即$l \leq x \leq r$），这个操作的贡献就是$x$，即我们需要快速求任意子数组的最大子段和，这可以用线段树来维护。

但是每个索引都用线段树独立维护的话肯定会超时，现在我也没想到有什么办法可以在线做，只想到用离线做。将所有询问$(k,l,r)$按照索引$k$分组，存入到数组$queries$中，$queries[k]$就是索引$k$上的所有询问列表，其中存的是三元组$(l,r,index)$，其中$index$是询问的编号。

可以从左往右扫描索引$i \in [1,n]$，对于每个索引$i$，将它左边的操作区间从线段树中剥离掉，而它右边的操作区间还没有遍历到，所以剩下的区间就是包括索引$i$的操作区间。为此还需要处理出一个$ops$数组，对于操作$i$ $(l,r,x)$，意味着扫描到达索引$l$的时候，线段树的$i$位置会多一个$x$，当扫描离开索引$r$的时候（$\gt r$），线段树的$i$位置会减去一个$x$。因此把二元组$(i,x)$追加到$ops[l]$中，二元组$(i,-x)$追加到$ops[r+1]$中，这样$ops[pos]$中就是所有和原数组$pos$位置相关的操作。然后遍历$i$位置上的询问$queries[i]$，对询问$(l,r,index)$，第$index$个询问的答案就是$[l,r]$上的最大子段和，用线段树查询即可。

复杂度分析

时间复杂度

预处理出$ops$数组和$queries$数组的时间复杂度为$O(n+m+q)$。遍历$i \in [1,n]$离线计算答案，对每个$i$需要遍历这个索引位置对应的操作，总共有$O(m)$级别的操作数量，每个操作有对线段树的修改操作，总时间复杂度为$O(mlog_2m)$。同理，还要遍历$i$对应的询问操作，一共有$O(q)$个操作，每个操作有对线段树的查询操作，时间复杂度为$O(qlog_2m)$。因此，整个算法的时间复杂度为$O(n+(m+q)log_2m)$。

空间复杂度

线段树的空间消耗为$O(m)$；$m$个操作需要存起来离线，每个索引上都要存对应操作，$ops$数组的空间消耗为$O(n+m)$；$q$个询问也需要存在每个索引上，$queries$数组的空间消耗为$O(n+q)$。至于线段树的递归消耗，是$O(log_2m)$级别的，在线性复杂度下不值一提。因此，整个算法的额外空间复杂度为$O(n+m+q)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, m, q;
LL ans[N];

class SegmentTree {
public:
    struct Info {
        LL sum, mx_sum, mx_pre, mx_suf;
        Info() {}
        Info(LL val): sum(val), mx_sum(val), mx_pre(val), mx_suf(val) {}
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(0LL);
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int pos, LL val) {
        modify(1, 1, m, pos, val);
    }

    Info query(int l, int r) {
        return query(1, 1, m, l, r);
    }

private:
    void modify(int u, int l, int r, int pos, LL val) {
        if(l == r) {
            seg[u] = Info(seg[u].sum + val);
        }else {
            int mid = l + r >> 1;
            if(pos <= mid) modify(u<<1, l, mid, pos, val);
            else modify(u<<1|1, mid + 1, r, pos, val);
            pushup(u);
        }
    }

    Info query(int u, int l, int r, int ql, int qr) {
        if(l == ql && r == qr) return seg[u];
        int mid = l + r >> 1;
        if(qr <= mid) {
            return query(u<<1, l, mid, ql, qr);
        }else if(mid < ql) {
            return query(u<<1|1, mid + 1, r, ql, qr);
        }else {
            return merge(query(u<<1, l, mid, ql, mid), query(u<<1|1, mid + 1, r, mid + 1, qr));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.sum = lchild.sum + rchild.sum;
        info.mx_sum = max({lchild.mx_sum, rchild.mx_sum, lchild.mx_suf + rchild.mx_pre});
        info.mx_pre = max(lchild.mx_pre, lchild.sum + rchild.mx_pre);
        info.mx_suf = max(rchild.mx_suf, rchild.sum + lchild.mx_suf);
        return info;
    }
};

int main() {
    scanf("%d%d", &n, &m);
    vector<array<int, 2>> ops[n + 2];
    for(int i = 1; i <= m; i++) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        ops[l].push_back({i, x});
        ops[r + 1].push_back({i, -x});
    }
    scanf("%d", &q);
    vector<array<int, 3>> queries[n + 1];
    for(int i = 1; i <= q; i++) {
        int k, s, t;
        scanf("%d%d%d", &k, &s, &t);
        queries[k].push_back({s, t, i});
    }
    SegmentTree seg;
    seg.build(1, 1, m);
    for(int i = 1; i <= n; i++) {
        for(auto&pir: ops[i]) {
            int index = pir[0], x = pir[1];
            seg.modify(index, x);
        }
        for(auto&query: queries[i]) {
            int l = query[0], r = query[1], index = query[2];
            ans[index] = seg.query(l, r).mx_sum;
        }
    }
    for(int i = 1; i <= q; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}