SPOJ - GSS1-Can you answer these queries I 线段树维护区间连续和最大值

时间：2023-03-08 17:17:22
SPOJ - GSS1-Can you answer these queries I 线段树维护区间连续和最大值

SPOJ - GSS1：https://vjudge.net/problem/SPOJ-GSS1

参考：http://www.cnblogs.com/shanyr/p/5710152.html?utm_source=itdadao&utm_medium=referral

题意：

　　给定一个数列，很多次询问，问某个区间中最大的连续和是多少。

思路

　　线段树，每个线段树的节点要维护对应区间的最大值ans，与左端点相连的最大值lv，与右端点相连的最大值rv，还有区间全部的总和V；

这个V用在pushup中。

这个pushup的操作是：

 void pushup(int rt){

                p[rt].v = p[rt<<].v + p[rt<<|].v;

                p[rt].lv = max(p[rt<<].lv, p[rt<<].v + p[rt<<|].lv);

                p[rt].rv = max(p[rt<<|].rv, p[rt<<|].v + p[rt<<].rv);

                p[rt].ans = max3(p[rt<<].ans, p[rt<<|].ans, p[rt<<].rv + p[rt<<|].lv);

            }

每个区间的lv 就是 （左子区间的lv  ，左子区间v + 右子区间的lv） 中的较大者。rv同理。

每个区间的ans就是，（左子区间的ans，右子区间的ans， 左子区间和右子区间中间连接的那段）中的较大者。

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

using namespace std;

//#pragma GCC optimize(3)

//#pragma comment(linker, "/STACK:102400000,102400000")  //c++

#define lson (l , mid , rt << 1)

#define rson (mid + 1 , r , rt << 1 | 1)

#define debug(x) cerr << #x << " = " << x << "\n";

#define pb push_back

#define pq priority_queue

#define max3(a,b,c) max(max(a,b),c)

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll ,ll > pll;

typedef pair<int ,int > pii;

typedef pair<int,pii> p3;

//priority_queue<int> q;//这是一个大根堆q

//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

#define fi first

#define se second

//#define endl '\n'

#define OKC ios::sync_with_stdio(false);cin.tie(0)

#define FT(A,B,C) for(int A=B;A <= C;++A)  //用来压行

#define REP(i , j , k)  for(int i = j ; i <  k ; ++i)

//priority_queue<int ,vector<int>, greater<int> >que;

const ll mos = 0x7FFFFFFF;  //

const ll nmos = 0x80000000;  //-2147483648

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f; //

const int mod = 1e9+;

const double esp = 1e-;

const double PI=acos(-1.0);

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/*-----------------------showtime----------------------*/

            const int maxn = ;

            int a[maxn];

            struct node

            {

                int lv,rv,v;

                int ans;

                node(){

                    lv = rv = v = ans = -inf;

                }

            }p[maxn<<];

            void pushup(int rt){

                p[rt].v = p[rt<<].v + p[rt<<|].v;

                p[rt].lv = max(p[rt<<].lv, p[rt<<].v + p[rt<<|].lv);

                p[rt].rv = max(p[rt<<|].rv, p[rt<<|].v + p[rt<<].rv);

                p[rt].ans = max3(p[rt<<].ans, p[rt<<|].ans, p[rt<<].rv + p[rt<<|].lv);

            }

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

                if(l==r){

                    p[rt].v = p[rt].lv = p[rt].rv = p[rt].ans = a[l];

                    return;

                }

                int mid = (l + r)>>;

                build(l,mid,rt<<);

                build(mid+,r,rt<<|);

                pushup(rt);

            }

            node query(int l,int r,int rt,int L,int R){

                if(l>=L&&r<=R){

                    return p[rt];

                }

                int mid = (l + r)>>;

                node t1,t2,res;

                t1.ans = -inf,t2.ans = -inf;

                if(mid >= L)t1 = query(l,mid,rt<<,L,R);

                if(mid < R) t2 = query(mid+,r,rt<<|,L,R);

                if(t1.ans!=-inf && t2.ans!=-inf){

                    res.lv = max(t1.lv, t1.v + t2.lv);

                    res.rv = max(t2.rv, t2.v + t1.rv);

                    res.v = t1.v + t2.v;

                    res.ans = max3(t1.ans, t2.ans, t1.rv + t2.lv);

                }

                else if(t1.ans!=-inf){

                    res = t1;

                }

                else if(t2.ans!=-inf){

                    res = t2;

                }

                return res;

            }

int main(){

            int n,m;

            scanf("%d", &n);

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

                scanf("%d", &a[i]);

            }

            build(,n,);

            scanf("%d", &m);

            while(m--){

                int l,r;

                scanf("%d%d", &l, &r);

                printf("%d\n", query(,n,,l,r).ans);

            }

            return ;

}

SPOJ - GSS1

相关文章