【BZOJ4094】[Usaco2013 Dec]Optimal Milking

Description

Farmer John最近购买了N(1 <= N <= 40000)台挤奶机，编号为1 ... N，并排成一行。第i台挤奶机每天能够挤M(i

)单位的牛奶 (1 < =M(i) <=100,000)。由于机器间距离太近，使得两台相邻的机器不能在同一天使用。Farmer Jo

hn可以自由选择不同的机器集合在不同的日子进行挤奶。在D(1 < = D < = 50,000)天中，每天Farmer John对某一

台挤奶机进行维护，改变该挤奶机的产量。Farmer John希望设计一个挤奶方案，使得挤奶机能够在D天后获取最多

的牛奶。

Input

第1行：两个整数N和D

第2..N+1行：每台挤奶机的M(i)

第N+2..N+D+1行：两个整数i和m，表示每天对机器i进行维护，机器i的产量为m。

Output

最大产量

Sample Input

5 3
1
2
3
4
5
5 2
2 7
1 10

Sample Output

32
【样例解释】
第1天，最优方案为2+4=6 ( 方案1+3+2一样)
第2天，最优方案为7+4=11
第3天，最优方案为10+3+2=15

题解：本题是一道有着奇妙区间合并方法的线段树

设s[x][k](k=0,1,2,3)表示当前区间，k&2代表左端点是否选择，k&1代表右端点是否选择

区间合并不难吧？

#include <cstdio>

#include <cstring>

#include <iostream>

#define lson x<<1

#define rson x<<1|1

using namespace std;

int n,m;

long long ans;

int s[200010][4];

int max(int x,int y,int z){return max(max(x,y),z);}

int max(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

void pushup(int x)

{

	for(int i=0;i<4;i++)

		s[x][i]=max(s[lson][i&2]+s[rson][2+(i&1)],s[lson][(i&2)+0]+s[rson][i&1],s[lson][(i&2)+1]+s[rson][i&1]);

}

void build(int l,int r,int x)

{

	if(l==r)

	{

		scanf("%d",&s[x][3]);

		return ;

	}

	int mid=l+r>>1;

	build(l,mid,lson),build(mid+1,r,rson);

	pushup(x);

}

void updata(int l,int r,int x,int y,int v)

{

	if(l==r)

	{

		s[x][3]=v;

		return ;

	}

	int mid=l+r>>1;

	if(y<=mid)	updata(l,mid,lson,y,v);

	else	updata(mid+1,r,rson,y,v);

	pushup(x);

}

int main()

{

	scanf("%d%d",&n,&m);

	build(1,n,1);

	int i,a,b;

	for(i=1;i<=m;i++)

	{

		scanf("%d%d",&a,&b);

		updata(1,n,1,a,b);

		ans+=max(s[1][0],s[1][1],s[1][2],s[1][3]);

	}

	printf("%lld",ans);

	return 0;

}

Farmer