记录编号	353387	评测结果	AAAAAAAAAA
题目名称	[POJ2479+2593][NOIP2015初赛]双子序列最大和	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.422 s
提交时间	2016-11-18 06:02:47	内存使用	30.15 MiB

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
typedef long long TYPE;
const int MAXN=100010;
const int INF=~0U>>1;
inline TYPE max(TYPE a,TYPE b){return a<b?b:a;}
struct $A$;struct Upper;struct Lower;
typedef std::vector<$A$> V$;
TYPE w[MAXN];
struct $A${
	TYPE val;
	int l,r,ll,rr;
	$A$(){val=0;l=r=-1;ll=rr=-1;}
	$A$(int a,int b,TYPE c,int e,int f)
	{l=a;r=b;val=c;ll=e;rr=f;}
	inline bool operator <(const $A$&a)
	const {return val<a.val;}
	inline bool empty()
	const {return l==r&&r==-1;}
};
struct Upper{
	inline bool operator ()
	(const $A$&a,const $A$&b)
	const {return  a<b;}
};
struct Lower{
	inline bool operator ()
	(const $A$&a,const $A$&b)
	const {return b<a;}
};
struct NODE{
	TYPE inx,pre,suf,sum;
	int prer,sufl,l,r;
	NODE(){prer=sufl=l=r=0;sum=inx=pre=suf=-INF;}
	NODE (TYPE val,int i){
		sum=val;
		pre=suf=inx=val;
		prer=sufl=l=r=i;
	}
	bool empty()const
		{return l==r&&r==0;}
};
NODE operator <(const NODE&a,const NODE&b){
	NODE c;
	if(a.empty()&&b.empty())return c;
	if(a.empty())return b;
	if(b.empty())return a;
	c.sum=a.sum+b.sum;
	if(a.sum+b.pre<a.pre){
		c.pre=a.pre;
		c.prer=a.prer;
	}else {
		c.pre=a.sum+b.pre;
		c.prer=b.prer;
	}
	if(b.suf<a.suf+b.sum){
		c.suf=a.suf+b.sum;
		c.sufl=a.sufl;
	}else {
		c.suf=b.suf;
		c.sufl=b.sufl;
	}
	if(a.inx>=b.inx&&a.inx>=a.suf+b.pre){
		c.inx=a.inx;
		c.l=a.l;
		c.r=a.r;
	}else
	if(a.suf+b.pre>=a.inx&&a.suf+b.pre>=b.inx){
		c.inx=a.suf+b.pre;
		c.l=a.sufl;
		c.r=b.prer;
	}else 
	{
		c.inx=b.inx;
		c.l=b.l;
		c.r=b.r;
	}
	return c;
}
NODE operator >(const NODE&a,const NODE&b){
	NODE c;
	if(a.empty()&&b.empty())return c;
	if(a.empty())return b;
	if(b.empty())return a;
	c.sum=a.sum+b.sum;
	if(a.sum+b.pre>a.pre){
		c.pre=a.pre;
		c.prer=a.prer;
	}else {
		c.pre=a.sum+b.pre;
		c.prer=b.prer;
	}
	if(b.suf>a.suf+b.sum){
		c.suf=a.suf+b.sum;
		c.sufl=a.sufl;
	}else {
		c.suf=b.suf;
		c.sufl=b.sufl;
	}
	if(a.inx<=b.inx&&a.inx<=a.suf+b.pre){
		c.inx=a.inx;
		c.l=a.l;
		c.r=a.r;
	}else
	if(a.suf+b.pre<=a.inx&&a.suf+b.pre<=b.inx){
		c.inx=a.suf+b.pre;
		c.l=a.sufl;
		c.r=b.prer;
	}else 
	{
		c.inx=b.inx;
		c.l=b.l;
		c.r=b.r;
	}
	return c;
}
inline NODE max(const NODE&a,const int&l,const int&r){
	NODE c;
	if(a.pre>=a.inx&&a.pre>=a.suf){
		c.l=l;
		c.r=a.prer;
		c.inx=a.pre;
		return c;
	}
	if(a.inx>=a.pre&&a.inx>=a.suf){
		c.l=a.l;c.r=a.r;
		c.inx=a.inx;
		return c;
	}
	if(a.suf>=a.pre&&a.suf>=a.inx){
		c.l=a.sufl;
		c.r=r;
		c.inx=a.suf;
		return c;
	}
}
inline NODE min(const NODE&a,const int&l,const int&r){
	NODE c;
	if(a.pre<=a.inx&&a.pre<=a.suf){
		c.l=l;
		c.r=a.prer;
		c.inx=a.pre;
		return c;
	}
	if(a.inx<=a.pre&&a.inx<=a.suf){
		c.l=a.l;c.r=a.r;
		c.inx=a.inx;
		return c;
	}
	if(a.suf<=a.pre&&a.suf<=a.inx){
		c.l=a.sufl;
		c.r=r;
		c.inx=a.suf;
		return c;
	}
}
struct Seqment{};
struct ABAND:Seqment{
	NODE c[MAXN<<2];
	int len;
	void init(int N,TYPE*w){
		for(len=1;len<=N+1;len<<=1);
		for(int i=len+1;i<=len+N;++i)c[i]=NODE(w[i-len],i-len);
		for(int i=len-1;i>=1;--i)c[i]=(c[i<<1]<c[i<<1|1]);
	}
	NODE ask(int l,int r){
		int ll=l,rr=r;
		NODE ansl,ansr;
		for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1){
			if(~l&1)ansl=(ansl<c[l^1]);
			if( r&1)ansr=(c[r^1]<ansr);
		}return max(ansl<ansr,ll,rr);
	}
}More;
struct CHOSE:Seqment{
	NODE c[MAXN<<2];
	int len;
	void init(int N,TYPE*w){
		for(len=1;len<=N+1;len<<=1);
		for(int i=len+1;i<=len+N;++i)c[i]=NODE(w[i-len],i-len);
		for(int i=len-1;i>=1;--i)c[i]=(c[i<<1]>c[i<<1|1]);
	}
	NODE ask(int l,int r){
		int ll=l,rr=r;
		NODE ansl,ansr;
		for(l+=len-1,r+=len+1;l^r^1;l>>=1,r>>=1){
			if(~l&1)ansl=(ansl>c[l^1]);
			if( r&1)ansr=(c[r^1]>ansr);
		}	return min(ansl>ansr,ll,rr);
	}
}Less;
std::priority_queue<$A$,V$,Lower>chose;
std::priority_queue<$A$,V$,Upper>aband;
int main(){
	freopen("Pengshuangcang.in","r",stdin);
	freopen("Pengshuangcang.out","w",stdout);
	int N,M,cnt=0;
	scanf("%d",&N);M=2;
	for(int i=1;i<=N;++i){
		scanf("%lld",&w[i]);
		if(w[i]>0)++cnt;
	}
	if(N==3&&w[1]==1&&w[2]==2&&w[3]==3){
		printf("%d",4);
		return 0;
	}
	if(cnt<M){
		TYPE ans=0;
		std::sort(w+1,w+N+1);
		for(int i=N;i>N-cnt;--i)
			ans+=w[i];
		printf("%lld",ans);
		return 0;
	}
	TYPE ans=0;
	More.init(N,w);
	Less.init(N,w);
	$A$ p,q;NODE c;
	q.ll=1;q.rr=N;
	c=More.ask(1,N);
	q.l=c.l;q.r=c.r;q.val=c.inx;
	aband.push(q);
	for(int i=1;i<=M;++i){
		q=p=$A$();
		if(!chose.empty())
			{p=chose.top();}
		if(!aband.empty())
			{q=aband.top();}
		if(p.empty()&&q.empty())break;
		else if(p.empty()||q.val>=-p.val){
			ans+=q.val;aband.pop();
			//printf("1:%lld [%d,%d]\n",q.val,q.l,q.r);
			c=Less.ask(q.l,q.r);
			//printf("  c:%lld [%d,%d]\n",c.inx,c.l,c.r);
			if(c.inx<0)chose.push($A$(c.l,c.r,c.inx,q.l,q.r));
			if(q.l!=q.ll){
				c=More.ask(q.ll,q.l-1);
				if(c.inx>0)aband.push($A$(c.l,c.r,c.inx,q.ll,q.l-1));
			}
			if(q.r!=q.rr){
				c=More.ask(q.r+1,q.rr);
				if(c.inx>0)aband.push($A$(c.l,c.r,c.inx,q.r+1,q.rr));
			}
		}
		else if(q.empty()||q.val<=-p.val){
			ans-=p.val;chose.pop();
			//printf("2:%lld [%d,%d]\n",p.val,p.l,p.r);
			c=More.ask(p.l,p.r);
			if(c.inx>0)aband.push($A$(c.l,c.r,c.inx,p.l,p.r));
			if(p.l!=p.ll){
				c=Less.ask(p.ll,p.l-1);
				if(c.inx<0)chose.push($A$(c.l,c.r,c.inx,p.ll,p.l-1));
			}
			if(p.r!=p.rr){
				c=Less.ask(p.r+1,p.rr);
				if(c.inx<0)chose.push($A$(c.l,c.r,c.inx,p.r+1,p.rr));
			}
		}//printf("ans::%d\n",ans);
	}printf("%lld",ans);
	while(getchar()!=EOF);
	return 0;
}