[SPOJ GSS3] Can you answer these queries III

SPOJ GSS3

思路

SPOJ GSS1差不多

代码

#include <iostream>
#include <cstdio>

int N;

class SegTree{
private:
    struct Data{
        int mx, lmx, rmx, sum;
        Data() : mx(0), lmx(0), rmx(0), sum(0){}
    };
    
    static Data merge(Data _, Data __){
        Data ans;
        ans.lmx=std::max(_.lmx, _.sum+__.lmx);
        ans.rmx=std::max(__.rmx, __.sum+_.rmx);
        ans.mx=std::max(ans.lmx, ans.rmx);
        ans.mx=std::max(ans.mx, _.rmx+__.lmx);
        ans.mx=std::max(ans.mx, std::max(_.mx, __.mx));
        ans.sum=_.sum+__.sum;
        return ans;
    }

    struct SNode{
        int l, r;
        Data val;
        SNode *lch, *rch;
        SNode(int l, int r, SNode *lch, SNode *rch) : l(l), r(r), lch(lch), rch(rch){}
        void push_up(){val=merge(lch->val, rch->val);}
    }*root;
    
    SNode *build(int l, int r){
        SNode *v;
        if(l==r){
            v=new SNode(l, r, NULL, NULL);
            scanf("%d", &v->val.sum); 
            v->val.lmx=v->val.rmx=v->val.mx=v->val.sum;
            return v;
        }
        v=new SNode(l, r, build(l, (l+r)/2), build((l+r)/2+1, r));
        v->push_up();
        return v;
    }
    
    void modify(SNode *v, int p, int val){
    	if(v->l==v->r){
    		v->val.lmx=v->val.rmx=v->val.mx=v->val.sum=val;
    		return;
    	}
    	if(2*p<=v->l+v->r) modify(v->lch, p, val);
    	else			   modify(v->rch, p, val);
    	v->push_up();
    }
    
    Data query(SNode *v, int l, int r){
        if(l<=v->l && v->r<=r) return v->val;
        if(2*l<=v->l+v->r && 2*r>v->l+v->r) return merge(query(v->lch, l, r), query(v->rch, l, r));
        if(2*l<=v->l+v->r) return query(v->lch, l, r);
        if(2*r>v->l+v->r)  return query(v->rch, l, r);
    }
    
public:
    SegTree(){
        root=build(1, N);
    }
    
    int query(int l, int r){
        return query(root, l, r).mx;
    }
    
    void modify(int p, int val){
    	modify(root, p, val);
    }
};

int main(){
    int M, x, y, opt;
    scanf("%d", &N);
    SegTree *T=new SegTree;
    scanf("%d", &M);
    while(M--){
        scanf("%d%d%d", &opt, &x, &y);
        if(!opt) T->modify(x, y);
        else printf("%d\n", T->query(x, y));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注