记录编号	83899	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]积木大赛	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2013-12-07 19:53:35	内存使用	10.23 MiB

#include<stdio.h>
#include<queue>
using std::queue;

const int MAXN=100000+10;

void open(){
	freopen("BlockNOIP2013.in","r",stdin);
	freopen("BlockNOIP2013.out","w",stdout);
}

void close(){
	fclose(stdin);
	fclose(stdout);
}

struct qujian{
	int a,b;
	qujian(int i,int j){
		a=i;
		b=j;
	}
};

struct node{
	int a,b;
	int m;
	int num;
	int lazy;
}tree[MAXN*5];

inline int mid(int a,int b){return (a+b)/2;}
inline int parent(int i){return i/2;}
inline int left(int i){return 2*i;}
inline int right(int i){return 2*i+1;} 
inline int min(int a,int b){return a>b?b:a;}

int hi[MAXN]={0};
int n;
queue<qujian> wait_slove;
queue<int> zero;

void read(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&hi[i]);
}


int build_tree(int i,int a,int b){
	node &t=tree[i];
	t.a=a;t.b=b;
	t.m=mid(a,b);
	t.lazy=0;
	if(a==b){
		t.num=hi[a];
		return t.num;
	}
	t.num=min(build_tree(left(i),a,t.m),build_tree(right(i),t.m+1,b));
	return t.num;
}

void up_lazy(int i){
     node &t=tree[i];
     if(left(i)<MAXN*5){
     tree[left(i)].num-=t.lazy;
     tree[left(i)].lazy+=t.lazy;
     }
         if(right(i)<MAXN*5){
     tree[right(i)].num-=t.lazy;
     tree[right(i)].lazy+=t.lazy;
     }
     t.lazy=0;
}

int get_min(int i,int a,int b){
	node &t=tree[i];
	
	up_lazy(i);
	
	if(t.a==t.b)return t.num;
	if(a>t.m)return get_min(right(i),a,b);
	if(b<=t.m)return get_min(left(i),a,b);
		
	return min( get_min(left(i),a,t.m) , get_min(right(i),t.m+1,b) );
}

void tree_eul(int i,int a,int b,int m){
	node &t=tree[i];
	t.num-=m;//gengxin
	up_lazy(i);//xia mian dou jian
	if((t.a==a && t.b==b))
    {
               t.lazy=m;
               return ;
    }
    
	if(a>t.m){
		tree_eul(right(i),a,b,m);
		return ;
	}
	if(b<=t.m){
		tree_eul(left(i),a,b,m);
		return ;
	}
	
	tree_eul(left(i),a,t.m,m);
	tree_eul(right(i),t.m+1,b,m);
}

void get_zero(int i,int a,int b){
	node &t=tree[i];
	up_lazy(i);
	if(t.a==t.b){
		if(t.num<=0)zero.push(a);
		return ;
	};
	if(t.num>0)return;
	if(a>t.m){
		get_zero(right(i),a,b);
		return ;
	}
	if(b<=t.m){
		get_zero(left(i),a,b);
		return ;
	}
	get_zero(left(i),a,t.m);
	get_zero(right(i),t.m+1,b);
}
	
void inc_qujian(int a,int b){
	int t_l;
	if(zero.empty())return ;
	int t=zero.front();
	zero.pop();
	if(t-1>=a)wait_slove.push(qujian(a,t-1));
	t_l=t;
	
	while(!zero.empty()){
		t=zero.front();
		zero.pop();
		if(t-1>=t_l+1){
			wait_slove.push(qujian(t_l+1,t-1));
		}
		t_l=t;
	}
	if(b>=t_l+1)wait_slove.push(qujian(t_l+1,b));
}

int solve(){
	wait_slove.push(qujian(1,n));
	int ans=0;
	while(!wait_slove.empty()){
		qujian q=wait_slove.front();
		wait_slove.pop();
		
		//printf("%d %d\n",q.a,q.b);
		
		int m=get_min(1,q.a,q.b);
		if(m){
			ans+=m;
			tree_eul(1,q.a,q.b,m);
		}
		
		while(!zero.empty())zero.pop();
			
		get_zero(1,q.a,q.b);
		inc_qujian(q.a,q.b);
	}
	return ans;
}
int main(){
	open();
	read();
	build_tree(1,1,n);
	int ans=solve();
	printf("%d",ans);
	close();
	return 0;
}