讲课专用——线段树—

题目链接：http://codevs.cn/problem/3981/

题解：

线段树求GSS模板题

一、一段长的区间的 GSS 有三种情况：
>1 完全在左子区间
>2 完全在右子区间
>3 横跨左右区间

二、需维护的信息：

mx 区间GSS ——用来更新情况1、2

lmx 区间最大前缀——用来更新情况3

rmx 区间最大后缀——用来更新情况3

sum 区间和——lmx，rmx

三、建树

1、初始化：区间需维护的信息最初都赋为输入值

2、合并区间信息

mx：3种情况中的最大值

lmx：左区间的lmx，左区间的sum+右区间lmx 取大

rmx 同理

四、查询

情况1、2很简单

情况3的合并与上面的合并区间信息同理

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

#define N 200000

#define inf -1e18

typedef long long LL;

int n,m;

int L,R;

struct node

{

    LL lmx,rmx,mx,sum;

    void clear()

    {

        lmx=rmx=sum=mx=inf;

    }

}tree[N*+]; 

template <typename T>

void read(T &x) //读入优化

{

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

    while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

void out(LL ans) //输出优化

{

    if(ans<) { putchar('-'); ans=-ans; }

    char s[];  int len=;

    do s[++len]=ans%+''; while(ans/=);

    while(len) putchar(s[len--]); putchar('\n');

}

void up(int k) //线段树上区间信息合并

{

    int l=k<<,r=k<<|;

    tree[k].mx=max(tree[l].mx,tree[r].mx);

    tree[k].mx=max(tree[k].mx,tree[l].rmx+tree[r].lmx);

    tree[k].lmx=max(tree[l].lmx,tree[l].sum+tree[r].lmx);

    tree[k].rmx=max(tree[r].rmx,tree[r].sum+tree[l].rmx);

    tree[k].sum=tree[l].sum+tree[r].sum;

}

void build(int k,int l,int r) //建树

{

    if(l==r)

    {

        read(tree[k].mx);

        tree[k].lmx=tree[k].rmx=tree[k].sum=tree[k].mx;

        return;

    }

    int mid=l+r>>;

    build(k<<,l,mid);

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

    up(k);

}

node query(int k,int l,int r) // 查询

{

    if(l>=L&&r<=R) return tree[k];

    int mid=l+r>>;

    if(R<=mid) return query(k<<,l,mid); //查询区间完全在左子区间

    if(L>mid) return query(k<<|,mid+,r); //查询区间完全在右子区间

    //查询区间跨左右区间

    node lans; lans.clear();

    lans=query(k<<,l,mid);

    node rans; rans.clear();

    rans=query(k<<|,mid+,r);

    node ans;

    ans.clear();

    ans.mx=max(lans.mx,rans.mx); //GSS完全在左或右区间

    ans.mx=max(lans.rmx+rans.lmx,ans.mx); //GSS跨左右区间

    ans.lmx=max(lans.lmx,lans.sum+rans.lmx);

    ans.rmx=max(rans.rmx,rans.sum+lans.rmx);

    ans.sum=lans.sum+rans.sum;

    return ans;

}

void init()

{

    read(n);

    build(,,n);

    read(m);

    LL ans;

    for(int i=;i<=m;++i)

    {

        read(L); read(R);

        ans=query(,,n).mx;

        out(ans);

    }

}

int main()

{

    init();

    return ;

}

巴特西

讲课专用——线段树——BSS

最新文章

热门文章