SPOJ GSS1 Can you answer these queries I[线段树]

Description

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

动态最大子段和
维护区间和sum，最大连续和mx，最大前缀和pre，最大后缀和suf
用了三个查询，子段，前缀和后缀
考虑最大的起点和终点位置然后更新

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define m ((l+r)>>1)

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define lc o<<1

#define rc o<<1|1

using namespace std;

typedef long long ll;

const int N=5e5+,INF=2e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,q,x,y;

struct node{

    int sum,mx,pre,suf;

}t[N<<];

void merge(int o){

    t[o].sum=t[lc].sum+t[rc].sum;

    t[o].mx=max(t[lc].suf+t[rc].pre,max(t[lc].mx,t[rc].mx));

    t[o].pre=max(t[lc].pre,t[lc].sum+t[rc].pre);

    t[o].suf=max(t[rc].suf,t[rc].sum+t[lc].suf);

}

void build(int o,int l,int r){

    if(l==r) t[o].sum=t[o].mx=t[o].pre=t[o].suf=read();

    else{

        build(lson);

        build(rson);

        merge(o);

    }

}

int qpre(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[o].pre;

    else if(qr<=m) return qpre(lson,ql,qr);

    else return max(qpre(lson,ql,qr),t[lc].sum+qpre(rson,ql,qr));

}

int qsuf(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[o].suf;

    else if(m<ql) return qsuf(rson,ql,qr);

    else return max(t[rc].suf,t[rc].sum+qsuf(lson,ql,qr));

}

int qmx(int o,int l,int r,int ql,int qr){

    if(ql<=l&&r<=qr) return t[o].mx;

    else{

        int ans=-INF;

        if(ql<=m) ans=max(ans,qmx(lson,ql,qr));

        if(m<qr) ans=max(ans,qmx(rson,ql,qr));

        if(ql<=m&&m<qr) ans=max(ans,qsuf(lson,ql,qr)+qpre(rson,ql,qr));

        return ans;

    }

}

int main(){

    n=read();

    build(,,n);

    q=read();

    for(int i=;i<=q;i++){

        x=read();y=read();

        printf("%d\n",qmx(,,n,x,y));

    }

}

巴特西

SPOJ GSS1 Can you answer these queries I[线段树]

Input

Output

Example

最新文章

热门文章