上海赛之前复习+提升一下..
Z K W 线段树是自底向上的线段树
相当于先遍历到最底层然后存起来
每次遍历再向上走
这对于有些有遍历到底部的线段树是极好的..
看了 Z K W 的 统计的力量(百度文库PPT) 后有种醍醐灌顶的感觉 他对数据结构的本质理解的非常透彻
这是不去上数据结构课的后果吗 - -?
对于这道题来说要有一种递归的思想
我就是少了这种思想所以怎么求 每个节点 的每个参数 就想了很久 - -||
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 50000 , INF = -0xffffff; inline int max(int a,int b,int c) { return max(a,max(b,c)); } struct node { int l,r,m,s; void init(int v=INF) { l=r=m=s=v; } ///left sum , right sum , max sum , sum; }; struct zst { node st[MAXN<<3]; int sz; void init(int n) { int i; for(sz=1;sz<=n+1;sz<<=1); st[sz].init(); for(i=sz+1;i<=sz+n;i++) { int t; scanf("%d",&t); st[i].init(t); } for(int end=sz<<1;i<end;i++) st[i].init(); for(i=sz-1;i>0;i--) { node &ls=st[i<<1],&rs=st[i<<1|1],&u=st[i]; u.s=ls.s+rs.s; u.l=max(ls.s + rs.l,ls.l); u.r=max(rs.s + ls.r,rs.r); int &mx=u.m; mx=INF; mx=max(ls.m,rs.m); mx=max(ls.r+rs.l,mx); } } int quire(int l,int r) { int msum,lsum,rsum; msum=lsum=rsum=INF; for(l+=sz-1,r+=sz+1;l^r^1;l>>=1,r>>=1) { if(~l&1) { msum=max(msum,st[l^1].m,lsum+st[l^1].l); lsum=max(st[l^1].s+lsum,st[l^1].r); } if(r&1) { msum=max(msum,st[r^1].m,rsum+st[r^1].r); rsum=max(st[r^1].s+rsum,st[r^1].l); } } return max(max(lsum,rsum,msum),rsum+lsum); } }st; int main() { //freopen("GSS1.in","r",stdin); int n; scanf("%d",&n); st.init(n); scanf("%d",&n); while(n--) { int a,b; scanf("%d %d",&a,&b); printf("%d\n",st.quire(a,b)); } return 0; } /* sample 1: 5 -1 -1 -1 1 1 5 1 1 1 2 1 3 1 4 1 5 out: -1 -1 -1 1 2 */