题目描述
难度分:2100
输入n(1≤n≤105),m(1≤m≤105)。
一开始有一个长为n的数组a,所有a[i]都是0。下标从1开始。
然后输入m个操作,每个操作输入l,r(1≤l≤r≤n),x(−105≤x≤105),表示把a的下标[l,r]中的元素都增加x。
然后输入q(1≤q≤105)和q个询问,每个询问输入k(1≤k≤n),s,t(1≤s≤t≤m)。
对于每个询问,你需要选择l和r,满足s≤l≤r≤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≤x≤r),这个操作的贡献就是x,即我们需要快速求任意子数组的最大子段和,这可以用线段树来维护。
但是每个索引都用线段树独立维护的话肯定会超时,现在我也没想到有什么办法可以在线做,只想到用离线做。将所有询问(k,l,r)按照索引k分组,存入到数组queries中,queries[k]就是索引k上的所有询问列表,其中存的是三元组(l,r,index),其中index是询问的编号。
可以从左往右扫描索引i∈[1,n],对于每个索引i,将它左边的操作区间从线段树中剥离掉,而它右边的操作区间还没有遍历到,所以剩下的区间就是包括索引i的操作区间。为此还需要处理出一个ops数组,对于操作i (l,r,x),意味着扫描到达索引l的时候,线段树的i位置会多一个x,当扫描离开索引r的时候(>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∈[1,n]离线计算答案,对每个i需要遍历这个索引位置对应的操作,总共有O(m)级别的操作数量,每个操作有对线段树的修改操作,总时间复杂度为O(mlog2m)。同理,还要遍历i对应的询问操作,一共有O(q)个操作,每个操作有对线段树的查询操作,时间复杂度为O(qlog2m)。因此,整个算法的时间复杂度为O(n+(m+q)log2m)。
空间复杂度
线段树的空间消耗为O(m);m个操作需要存起来离线,每个索引上都要存对应操作,ops数组的空间消耗为O(n+m);q个询问也需要存在每个索引上,queries数组的空间消耗为O(n+q)。至于线段树的递归消耗,是O(log2m)级别的,在线性复杂度下不值一提。因此,整个算法的额外空间复杂度为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;
}