Can you answer these queries I SPOJ - GSS1 You are given a sequence A[1], A[2], …, A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: Query(x,y) = Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }. Given M queries, your PRogram must output the results of these queries. Input The first line of the input file contains the integer N. In the second line, N numbers follow. The third line contains the integer M. M lines follow, where line i contains 2 numbers xi and yi. Output Your program should output the results of the M queries, one query per line. Example Input: 3 -1 2 3 1 1 2 Output: 2
/*一开始W.不知道为啥.拍了好多组数据都OK.原来case更新的时候错了.考虑三种情况.分别维护GSS,LGSS,RGSS.分为两种形态:跨区间和不跨区间. case 1,2:左右段的GSS.case 3:左段右端与右段左端的GSS和.一开始更新的时候更新成了该段的左端GSS 右端GSS case3.画了画图不对吖.如果跨区间的话这两种情况是包含在case3里边的.然后这样就忽略了case1,2. */#include<iostream>#include<cstdio>#define MAXN 50001using namespace std;int n,m,cut;struct data{ int l,r,lg,rg,g,sum,size; data *lc,*rc;}tree[MAXN*4];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void build(data *k,int l,int r,int now){ k->l=l,k->r=r; if(l==r) {k->g=k->lg=k->rg=k->sum=read();return ;} int mid=(l+r)>>1; k->size=now; k->lc=&tree[now*2]; k->rc=&tree[now*2+1]; k->lc->size=now*2; k->rc->size=now*2+1; build(k->lc,l,mid,now*2); build(k->rc,mid+1,r,now*2+1); k->lg=max(k->lc->lg,k->lc->sum+k->rc->lg); k->rg=max(k->rc->rg,k->rc->sum+k->lc->rg); k->sum=k->lc->sum+k->rc->sum; k->g=max(k->lc->g,max(k->lc->rg+k->rc->lg,k->rc->g)); return ;}data query(data *k,int l,int r,int num){ data xx; if(l<=k->l&&k->r<=r) return tree[num]; int mid=(k->l+k->r)>>1; if(l>mid) return query(k->rc,l,r,k->rc->size); else if(r<=mid) return query(k->lc,l,r,k->lc->size); else { data ll=query(k->lc,l,mid,k->lc->size); data rr=query(k->rc,mid+1,r,k->rc->size); xx.sum=ll.sum+rr.sum; xx.lg=max(ll.lg,ll.sum+rr.lg); xx.rg=max(rr.rg,rr.sum+ll.rg); xx.g=max(ll.g,max(rr.g,ll.rg+rr.lg)); } return xx;}int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); int x,y; n=read(); build(tree+1,1,n,1); m=read(); while(m--) { x=read(),y=read(); data xx=query(tree+1,x,y,1); printf("%d/n",xx.g); } return 0;}新闻热点
疑难解答
