题目描述
FJ 最近买了 1 个新仓库, 内含 N 个挤奶机,1 到 N 编号并排成一行。
挤奶机 i 每天能产出 M(i) 单位的奶。不幸的是, 机器装得太近以至于如果一台机器i 在某天被使用, 那与它相邻的两台机器那一天不能被使用(当然, 两端点处的机器分别只有一个与之相邻的机器)。
FJ 可自由选择不同的机器在不同的日子工作。
FJ 感兴趣于计算在 D 天内他能产出奶的最大值。在每天开始时, 他有足够的时间维护一个选中的挤奶机i, 从而改变它从那天起的每日产奶量 M(i)。
给出这些每日的修改,请告诉 FJ 他 D 天中能产多少奶。
题意简述
给定 n 个点排成一排，每个点有一个点权，多次改变某个点的点权并将最大点独立集计入答案，输出最终的答案
思路
记 tree[root][0/1][0/1] 表示以 root 为根的线段树左右区间选/不选的答案，直接合并就好
/************************************************
*Author : lrj124
*Created Time : 2019.11.06.21:55
*Mail : 1584634848@qq.com
*Problem : luogu3097
************************************************/
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 40000 + 10;
int n,d,tree[maxn<<2][2][2];
long long ans;
inline void pushup(int root) {
tree[root][0][1] = max(max(
tree[root<<1][0][1]+tree[root<<1|1][0][1],
tree[root<<1][0][0]+tree[root<<1|1][0][1]),
tree[root<<1][0][0]+tree[root<<1|1][1][1]);
tree[root][1][0] = max(max(
tree[root<<1][1][0]+tree[root<<1|1][1][0],
tree[root<<1][1][1]+tree[root<<1|1][0][0]),
tree[root<<1][1][0]+tree[root<<1|1][0][0]);
tree[root][0][0] = max(max(
tree[root<<1][0][1]+tree[root<<1|1][0][0],
tree[root<<1][0][0]+tree[root<<1|1][0][0]),
tree[root<<1][0][0]+tree[root<<1|1][1][0]);
tree[root][1][1] = max(max(
tree[root<<1][1][1]+tree[root<<1|1][0][1],
tree[root<<1][1][0]+tree[root<<1|1][1][1]),
tree[root<<1][1][0]+tree[root<<1|1][0][1]);
}
inline void build(int l,int r,int root) {
if (l == r) {
scanf("%d",&tree[root][1][1]);
return;
}
int mid = l+r>>1;
build(l,mid,root<<1);
build(mid+1,r,root<<1|1);
pushup(root);
}
inline void update(int l,int r,int num,int x,int root) {
if (l > num || r < num) return;
if (l == r) {
tree[root][1][1] = x;
return;
}
int mid = l+r>>1;
update(l,mid,num,x,root<<1);
update(mid+1,r,num,x,root<<1|1);
pushup(root);
}
int main() {
// freopen("luogu3097.in","r",stdin);
// freopen("luogu3097.out","w",stdout);
scanf("%d%d",&n,&d);
build(1,n,1);
for (int i = 1,x,y;i <= d;i++) {
scanf("%d%d",&x,&y);
update(1,n,x,y,1);
ans += max(max(tree[1][0][1],tree[1][1][0]),max(tree[1][1][1],tree[1][0][0]));
}
printf("%lld",ans);
return 0;
}