2016百度之星初赛Astar Round2B - 区间的价值

网友投稿 297 2022-08-25

2016百度之星初赛Astar Round2B - 区间的价值

题意:

定义一个区间的价值为区间的最大数*最小数。现给了n(1≤n≤100000)个数，问1~n长度的最大价值分别是多少。

题解:

Code:

#include#include#include#include#include#include#include#include#include#define ll long longusing namespace std;const int MAXN=100005;ll MAX[MAXN<<2],MIN[MAXN<<2],A[MAXN],ANS[MAXN];void updateMAX(int x,int l,int r,int now){ if (l==r){ MAX[now]=l; return; } int mid=(l+r)>>1; if (x<=mid) updateMAX(x,l,mid,now<<1); else updateMAX(x,mid+1,r,(now<<1)|1); if (A[MAX[now<<1]]>A[MAX[now<<1|1]]) MAX[now]=MAX[now<<1]; else MAX[now]=MAX[now<<1|1];}void updateMIN(int x,int l,int r,int now){ if (l==r){ MIN[now]=l; return; } int mid=(l+r)>>1; if (x<=mid) updateMIN(x,l,mid,now<<1); else updateMIN(x,mid+1,r,(now<<1)|1); if (A[MIN[now<<1]]=L && r<=R) return MAX[now]; int mid=(l+r)>>1,a=0,b=0; if (L<=mid) a=queryMAX(l,mid,L,R,now<<1); if (R>mid) b=queryMAX(mid+1,r,L,R,now<<1|1); if (a==0) return b; if (b==0) return a; if (A[a]>A[b]) return a; return b;}int queryMIN(int l,int r,int L,int R,int now){ if (l>=L && r<=R) return MIN[now]; int mid=(l+r)>>1,a=0,b=0; if (L<=mid) a=queryMIN(l,mid,L,R,now<<1); if (R>mid) b=queryMIN(mid+1,r,L,R,now<<1|1); if (a==0) return b; if (b==0) return a; if (A[a]b) swap(a,b); ll d=A[a]*A[b]; for (int i=(b-a+1);i<=(r-l+1);i++) ANS[i]=max(ANS[i],d); if (A[b]>A[a]) dfs(a+1,r,n),dfs(l,a-1,n); else dfs(b+1,r,n),dfs(l,b-1,n);}int main(){ int n; // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); while (~scanf("%d",&n)){ memset(MAX,0,sizeof(MAX)); memset(MIN,0,sizeof(MIN)); for (int i=1;i<=n;i++){ scanf("%I64d",&A[i]); updateMAX(i,1,n,1); updateMIN(i,1,n,1); } memset(ANS,0,sizeof(ANS)); dfs(1,n,n); for (int i=1;i<=n;i++) printf("%I64d\n",ANS[i]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

上一篇:办卡不要钱还送礼品，这样的营销模式是怎么赚到钱的！（办卡送现金什么套路）
下一篇:gocv边界填充
相关文章

 发表评论

暂时没有评论，来抢沙发吧~