poj 2750 Potted Flower(線分ツリー+ダイナミックプランニング)

タイトルリンク:http://poj.org/problem?id=2750
△長いこと考えてもできなかったが、結局黙って問題解を見てしまった.
考え方:
sum:区間の和を表す
maxNum:区間最大値を示す
minNum:区間最小値を示す
lmax:区間左端からの連続最大サブシーケンスを表す
rmax:区間右端からの連続最大サブシーケンスを表す
lmin:区間左端からの連続最小子シーケンスを表す
rmin:区間右端からの連続最小子シーケンスを表す
allmax:区間最大自己シーケンスを表す
allmin:区間最小サブシーケンスを表す
状態遷移方程式:
//現在区間の和は左右サブ区間の和//現在区間の最大値は左右区間の最大値の最大値//現在区間の最小値は左右区間の最小値の最小値//現在区間の左端からの連続最大子系列は左区間の左端からの連続最大子系列と左区間の和に加えて右区間の左端からの連続最大子シーケンスの最大値//現在区間左端からの連続最大子シーケンス右端からの連続最大子シーケンス右端からの連続最大子シーケンス右端からの和左区間右端からの連続最大子シーケンスの最大値//現在区間左端からの連続最小子シーケンス左端からの連続最小子シーケンス左端からの連続最小サブシーケンス//現在区間左端からの連続最小サブシーケンス右端からの連続最小サブシーケンス右端からの連続最小サブシーケンス右端からの和左区間右端からの連続最小サブシーケンスの最小値//現在区間の最大サブシーケンス右端からの最大サブシーケンス右端からの最大サブシーケンス右区間を加えて左端からの最大子系列の最大値//現在区間の最小子系列は左右区間の最小子系列と左区間右端からの最小子系列に加えて左端からの最小子系列の最小値
最後に、区間全体の最大値を更新する必要があります(ループのため):
区間最大サブシーケンス<区間と-区間の最小サブシーケンス
区間最大自己シーケンス=区間および-区間の最小サブシーケンス
出力する場合も3つのケースを考慮する必要があります.
①全て正数:即ちnode[1].sum=node[1].allmax
②全て負数:即ちnode[1].sum=node[1].allmin
③以上の2つ以外の場合
実装の詳細については、コードを参照してください.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<math.h>
#include<algorithm>
using namespace std;

template<class T>inline T maxt(T a,T b,T c){return max(max(a,b),c);}
template<class T>inline T mint(T a,T b,T c){return min(min(a,b),c);}

const int INF=0x3f3f3f3f;
const int maxn=100010;
int T,n,m;

struct segmentTree{
	int l;
	int r;
	int sum;
	int maxNum,minNum;
	int lmax,rmax;
	int lmin,rmin;
	int allmax,allmin;
}node[3*maxn];

void PushUp(int rt){
	node[rt].sum=node[rt<<1].sum+node[rt<<1|1].sum;
	node[rt].maxNum=max(node[rt<<1].maxNum,node[rt<<1|1].maxNum);
	node[rt].minNum=min(node[rt<<1].minNum,node[rt<<1|1].minNum);
	node[rt].lmax=max(node[rt<<1].lmax,node[rt<<1].sum+node[rt<<1|1].lmax);
	node[rt].rmax=max(node[rt<<1|1].rmax,node[rt<<1|1].sum+node[rt<<1].rmax);
	node[rt].lmin=min(node[rt<<1].lmin,node[rt<<1].sum+node[rt<<1|1].lmin);
	node[rt].rmin=min(node[rt<<1|1].rmin,node[rt<<1|1].sum+node[rt<<1].rmin);
	node[rt].allmax=maxt(node[rt<<1].allmax,node[rt<<1|1].allmax,node[rt<<1].rmax+node[rt<<1|1].lmax);
	node[rt].allmin=mint(node[rt<<1].allmin,node[rt<<1|1].allmin,node[rt<<1].rmin+node[rt<<1|1].lmin);
}

void build(int rt,int l,int r){
	node[rt].l=l;
	node[rt].r=r;
	node[rt].maxNum=0;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}

void Update(int rt,int l,int r,int pos,int val){
	if(l==r){
		node[rt].sum=val;
		node[rt].maxNum=node[rt].minNum=node[rt].lmax=node[rt].rmax=val;
		node[rt].lmin=node[rt].rmin=node[rt].allmax=node[rt].allmin=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) Update(rt<<1,l,mid,pos,val);
	else Update(rt<<1|1,mid+1,r,pos,val);
	PushUp(rt);
}

void Function(){
	if(node[1].allmax<node[1].sum-node[1].allmin)
		node[1].allmax=node[1].sum-node[1].allmin;
}

void Output(){
	if(node[1].sum==node[1].allmax)
		printf("%d
",node[1].sum-node[1].minNum);
	else if(node[1].sum==node[1].allmin)
		printf("%d
",node[1].maxNum);
	else
		printf("%d
",node[1].allmax);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
#endif
	while(~scanf("%d",&n)){
		build(1,1,n);
		int a,b;
		for(int i=1;i<=n;i++){
			scanf("%d",&a);
			Update(1,1,n,i,a);
		}
		scanf("%d",&m);
		while(m--){
			scanf("%d%d",&a,&b);
			Update(1,1,n,a,b);
			Function();
			Output();
		}
	}
	return 0;
}