记录编号	418529	评测结果	AAAAAAAAAA
题目名称	[雅礼集训 2017] jump	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.765 s
提交时间	2017-06-30 17:12:04	内存使用	20.38 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,mn[maxn<<2],mx[maxn<<2],s,t,ans_min,ans_max;;
struct DS{
	int l[maxn],r[maxn];
	void build(int L,int R,int rt)const{
		if(L==R){
			mn[rt]=l[L];
			mx[rt]=r[L];
			return;
		}
		int mid=(L+R)>>1;
		build(L,mid,rt<<1);
		build(mid+1,R,rt<<1|1);
		mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
		mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
	}
	void query(int l,int r,int rt)const{
		if(s<=l&&t>=r){
			ans_min=min(ans_min,mn[rt]);
			ans_max=max(ans_max,mx[rt]);
			return;
		}
		int mid=(l+r)>>1;
		if(s<=mid)query(l,mid,rt<<1);
		if(t>mid)query(mid+1,r,rt<<1|1);
	}
	DS operator+(const DS &b)const{
		static DS c;
		build(1,n,1);
		for(int i=1;i<=n;i++){
			s=b.l[i];
			t=b.r[i];
			ans_min=(~0u)>>1;
			ans_max=1<<31;
			query(1,n,1);
			c.l[i]=ans_min;
			c.r[i]=ans_max;
		}
		return c;
	}
	operator bool()const{
		static int pmn[maxn];
		pmn[0]=(~0u)>>1;
		for(int i=1;i<=n;i++){
			pmn[i]=min(pmn[i-1],r[i]);
			if(pmn[l[i]-1]<i)return true;
		}
		return false;
	}
}pw[17],now,tmp;
int main(){
	freopen("jump2017.in","r",stdin);
	freopen("jump2017.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		pw[0].l[i]=max(i-x,1);
		pw[0].r[i]=min(i+x,n);
		now.l[i]=now.r[i]=i;
	}
	for(int i=1;i<17;i++)pw[i]=pw[i-1]+pw[i-1];
	int ans=0;
	for(int i=16;~i;i--)if((tmp=now+pw[i])){
		ans|=1<<i;
		now=tmp;
	}
	printf("%d",ans+1);
	return 0;
}
/*
8
7 1 1 1 1 1 1 7
*/