Can you answer these queries III

发布于 2018-10-02  374 次阅读


题目描述

题目链接

给定一个长度为 $n$ 的序列 $a$,有 $q$ 个询问,询问有两种:

  • 单点修改

  • 给定一组 $L,R$,求

    $$max{\Sigma_{i=l}^{r}a_i}(L\leq l \leq r \leq R)$$

其中 $n,q \leq 50000$。

解题报告

这个有和,我们可以用线段树维护。

线段树需要维护四个值:当前区间的前缀最大值,当前区间的后缀最大值,当前区间的答案,以及区间和。

这些显然可以通过线段树合并来实现。

前缀最大值 = max(左儿子的前缀最大值,左儿子的和 + 右儿子的前缀最大值)

后缀最大值 = max(右儿子的后缀最大值,右儿子的和 + 左儿子的后缀最大值)

答案 = max(左儿子的答案,右儿子的答案,左儿子的后缀最大值 + 右儿子的前缀最大值)

也就是考虑相交和不相交的部分然后合并了。

具体见代码。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define RFOR(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

namespace fastIO{ 
    #define BUF_SIZE 100000 
    #define OUT_SIZE 100000 
    #define ll long long 
    bool IOerror=0; 
    inline char nc(){ 
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
        if (p1==pend){ 
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
            if (pend==p1){IOerror=1;return -1;} 
        } 
        return *p1++; 
    } 
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 
    inline void read(int &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
    inline void read(ll &x){ 
        bool sign=0; char ch=nc(); x=0; 
        for (;blank(ch);ch=nc()); 
        if (IOerror)return; 
        if (ch=='-')sign=1,ch=nc(); 
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
        if (sign)x=-x; 
    } 
    #undef ll 
    #undef OUT_SIZE 
    #undef BUF_SIZE 
}; 
using namespace fastIO;

const int MAXN = 50000 + 5;

struct SegmentTree *New(int ,int ,SegmentTree *,SegmentTree *);

struct SegmentTree{
    int l,r;
    LL lmax,rmax,mmax,sum; //前缀 max,后缀 max,跨越终点 max,和。
    SegmentTree *lc,*rc;

    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return (l == r) ? New(l,r,NULL,NULL) : New(l,r,build(l,mid),build(mid+1,r));
    }

    inline void pushup(){
        sum = lc->sum + rc->sum;
        lmax = std::max(lc->lmax,lc->sum + rc->lmax);
        rmax = std::max(rc->rmax,lc->rmax + rc->sum);
        mmax = std::max(std::max(lc->mmax,rc->mmax),lc->rmax + rc->lmax);
    }

    inline void update(int pos,int x){
        if(l == r){
            lmax = rmax = mmax = sum = x;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) lc->update(pos,x);
        else rc->update(pos,x);
        pushup();
    }

    inline SegmentTree query(int L,int R){
        if(L == l && R == r)
            return (SegmentTree){0,0,lmax,rmax,mmax,sum,NULL,NULL};
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->query(L,R);
        if(L > mid) return rc->query(L,R);
        SegmentTree lans = lc->query(L,mid),rans = rc->query(mid + 1,R),ans;
        ans.lmax = std::max(lans.lmax,lans.sum + rans.lmax);
        ans.rmax = std::max(rans.rmax,rans.sum + lans.rmax);
        ans.sum = lans.sum + rans.sum;
        ans.mmax = std::max(std::max(lans.mmax,rans.mmax),lans.rmax + rans.lmax);
        return ans;
    }
}pool[MAXN<<2],*frog = pool,*segt;

SegmentTree *New(int l,int r,SegmentTree *lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;
    ret->lc = lc;ret->rc = rc;
    ret->lmax = ret->rmax = ret->mmax = INT_MIN;
    return ret;
}

int N,M;
int opt,x,y;
SegmentTree ans;

int main(){
    read(N);
    segt = SegmentTree::build(1,N);
    FOR(i,1,N){
        int x;
        read(x);
        segt->update(i,x);
    }
    read(M);
    while(M--){
        read(opt);read(x);read(y);
        if(opt){
            printf("%lld\n",segt->query(x,y).mmax);
        }
        else{
            segt->update(x,y);
        }
    }
    return 0;
}

一个OIer。