题目描述
难度分:2600
输入n(2≤n≤2×105),长为n的数组a(−109≤a[i]≤109),长为n的数组b(−109≤b[i]≤109),下标从1开始。
定义区间[i,j]的cost=a的子数组[i,j]的元素和+b[i]+b[j]。特别地,区间[i,i]的cost=a[i]+2×b[i]。
然后输入q(1≤q≤2×105)和q个询问,格式如下:
1 p x
,把a[p]改成x。其中1≤p≤n,−109≤x≤109。2 p x
,把b[p]改成x。其中1≤p≤n,−109≤x≤109。3 L R
,在区间[L,R]中选两个不重叠的非空区间,输出这两个区间的cost之和的最大值。其中1≤L<R≤n。
输入样例1
7
3 -1 4 -3 2 4 0
0 6 1 0 -3 -2 -1
6
3 1 7
1 2 0
3 3 6
2 5 -3
1 3 2
3 1 5
输出样例1
18
7
16
输入样例2
10
2 -1 -3 -2 0 4 5 6 2 5
2 -4 -5 -1 6 2 5 -6 4 2
10
3 6 7
1 10 -2
3 5 7
3 2 8
2 1 -5
2 7 4
3 1 3
3 3 8
3 2 3
1 4 4
输出样例2
23
28
28
-17
27
-22
算法
状态机DP
+线段树优化
状态定义
对于一段区间[l,r],设计状态
- f[0]当前还未选数。
- f[1]进行第一段的选数。
- f[2]第一段选完了。
- f[3]已经选完了第一段,进行第二段选数。
- f[4]两段都选完了。
状态转移
f[0]继承之前的状态就行。f[1]有两种可能:i是第一段的开始,从f[0]转移过来;i不是第一段的开始,从f[1]转移过来。f[2]有两种可能:第一段只有一个i,那么i既是开始也是结束,b[i]要加两遍,从f[0]转移过来;i只是结束,从f[1]转移过来。f[3]和f[1]类似,i可以是开始也可以是结束。f[4]和f[2]类似,可以既是开始也是结束;也可以仅是结束。状态转移方程如下,f′表示前一个状态:
- f[0]=f′[0]
- f[1]=max(f′[0]+a[i]+b[i],f′[1]+a[i])
- f[2]=max(f′[0]+a[i]+2×b[i],f′[1]+a[i]+b[i],f′[2])
- f[3]=max(f′[2]+a[i]+b[i],f′[3]+a[i])
- f[4]=max(f′[2]+a[i]+2×b[i],f′[3]+a[i]+b[i],f′[4])
状态转移矩阵为
A=(0a[i]+b[i]a[i]+2×b[i]−∞−∞−∞a[i]a[i]+b[i]−∞−∞−∞−∞0a[i]+b[i]a[i]+2×b[i]−∞−∞−∞a[i]a[i]+b[i]−∞−∞−∞−∞0)
转移的时候类似矩阵乘法,对于给定的从i转移到j,枚举左右两个孩子的转移中间点k。某段区间[l,r]上的答案就是0转移到4,即A[0][4]。
复杂度分析
时间复杂度
建立线段树的时间复杂度为O(nlog2n)。处理q个操作。每个操作会有对线段树的修改和查询操作,总的时间复杂度为O(qlog2n)。整个算法的时间复杂度为(n+q)log2n,但由于线段树的每个节点需要维护一个5×5的矩阵,所以这个O(log2n)的常数非常大。
空间复杂度
空间瓶颈就是线段树的空间,原本的空间复杂度为O(4n),但每个节点需要维护5×5的状态转移矩阵。所以额外空间复杂度为O(100n),是个常数很大的O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
const LL INF = 1e18;
int n, q, a[N], b[N];
class SegmentTree {
public:
struct Info {
int l, r;
LL f[5][5];
Info() {
memset(f, -0x3f, sizeof f);
for(int i = 0; i < 5; i++) {
f[i][i] = 0;
}
}
} seg[N<<2];
explicit SegmentTree() {}
void build(int u, int l, int r) {
if(l == r) {
seg[u].l = seg[u].r = r;
LL x = a[l], y = b[l];
seg[u].f[0][0] = 0;
seg[u].f[0][1] = x + y;
seg[u].f[1][1] = x;
seg[u].f[0][2] = x + 2 * y;
seg[u].f[1][2] = x + y;
seg[u].f[2][2] = 0;
seg[u].f[2][3] = x + y;
seg[u].f[3][3] = x;
seg[u].f[2][4] = x + 2 * y;
seg[u].f[3][4] = x + y;
seg[u].f[4][4] = 0;
}else {
int mid = l + r >> 1;
build(u<<1, l, mid);
build(u<<1|1, mid + 1, r);
pushup(u);
}
}
void modify(int pos) {
modify(1, pos);
}
Info query(int l, int r) {
return query(1, l, r);
}
private:
void modify(int u, int pos) {
if(seg[u].l == pos && seg[u].r == pos) {
LL x = a[pos], y = b[pos];
seg[u].f[0][0] = 0;
seg[u].f[0][1] = x + y;
seg[u].f[1][1] = x;
seg[u].f[0][2] = x + 2 * y;
seg[u].f[1][2] = x + y;
seg[u].f[2][2] = 0;
seg[u].f[2][3] = x + y;
seg[u].f[3][3] = x;
seg[u].f[2][4] = x + 2 * y;
seg[u].f[3][4] = x + y;
seg[u].f[4][4] = 0;
}else {
int mid = seg[u].l + seg[u].r >> 1;
if(pos <= mid) {
modify(u<<1, pos);
}else {
modify(u<<1|1, pos);
}
pushup(u);
}
}
Info query(int u, int l, int r) {
if(l <= seg[u].l && seg[u].r <= r) return seg[u];
int mid = seg[u].l + seg[u].r >> 1;
if(r <= mid) {
return query(u<<1, l, r);
}else if(mid < l) {
return query(u<<1|1, l, r);
}else {
return merge(query(u<<1, l, r), query(u<<1|1, l, r));
}
}
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.l = lchild.l;
info.r = rchild.r;
for(int i = 0; i < 5; i++) {
for(int j = 0; j < 5; j++) {
info.f[i][j] = -INF;
for(int k = 0; k < 5; k++) {
info.f[i][j] = max(info.f[i][j], lchild.f[i][k] + rchild.f[k][j]);
}
}
}
return info;
}
};
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
}
SegmentTree seg;
seg.build(1, 1, n + 1);
scanf("%d", &q);
while(q--) {
int t;
scanf("%d", &t);
if(t < 3) {
int p, x;
scanf("%d%d", &p, &x);
if(t == 1) {
a[p] = x;
}else {
b[p] = x;
}
seg.modify(p);
}else {
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", seg.query(l, r).f[0][4]);
}
}
return 0;
}