[文章目录]
Description
Farmer John最近购买了N(1 <= N <= 40000)台挤奶机，编号为1 ... N，并排成一行。第i台挤奶机每天能够挤M(i)单位的牛奶 (1 < =M(i) <=100,000)。由于机器间距离太近，使得两台相邻的机器不能在同一天使用。Farmer John可以自由选择不同的机器集合在不同的日子进行挤奶。在D(1 < = D < = 50,000)天中，每天Farmer John对某一台挤奶机进行维护，改变该挤奶机的产量。Farmer John希望设计一个挤奶方案，使得挤奶机能够在D天后获取最多的牛奶。
线段树维护区间两端点是否选择的最大挤奶产量即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[41000];
int t[161000][4];// 0:00 1:01 2:10 3:11
void pushup(int pos)
{
t[pos][0]=max(t[pos<<1][1]+t[pos<<1|1][0],max(t[pos<<1][0]+t[pos<<1|1][2],t[pos<<1][0]+t[pos<<1|1][0]));
t[pos][1]=max(t[pos<<1][0]+t[pos<<1|1][1],max(t[pos<<1][0]+t[pos<<1|1][3],t[pos<<1][1]+t[pos<<1|1][1]));
t[pos][2]=max(t[pos<<1][2]+t[pos<<1|1][0],max(t[pos<<1][2]+t[pos<<1|1][2],t[pos<<1][3]+t[pos<<1|1][0]));
t[pos][3]=max(t[pos<<1][2]+t[pos<<1|1][1],max(t[pos<<1][2]+t[pos<<1|1][3],t[pos<<1][3]+t[pos<<1|1][1]));
}
void build(int pos,int l,int r)
{
if(l==r)
{
t[pos][3]=w[l];
return ;
}
int mid=(l+r)>>1;
build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
pushup(pos);
}
void fix(int pos,int l,int r,int x,int y)
{
if(l==r)
{
t[pos][3]=y;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) fix(pos<<1,l,mid,x,y);
else fix(pos<<1|1,mid+1,r,x,y);
pushup(pos);
}
long long ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",w+i);
build(1,1,n); int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
fix(1,1,n,x,y);
ans+=max(max(t[1][0],t[1][1]),max(t[1][2],t[1][3]));
}
printf("%lld",ans);
return 0;
}