1 条题解

  • 1
    @ 2019-01-08 21:05:08
    /*
    线段树优化dp
    考虑最大子段和的生成情况,可得到如下方程:
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
    tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
    tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
    tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
    sum是区间和
    lmax是紧靠区间左端点的最大子段和
    rmax是紧靠区间右端点的最大子段和
    dat是整个区间的最大子段和
    */
    #define method_1
    #ifdef method_1
    /*
    
    */
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=500000+5;
    const int INF=0x3f3f3f3f;
    int n,m,a[maxn];
    struct node {
        int l,r,sum,lmax,rmax,dat;
        node(int tmp=0) {
            sum=lmax=rmax=dat=tmp;
        }
    } tree[maxn<<2];
    void build(int p,int l,int r) {
        tree[p].l=l,tree[p].r=r;
        if(l==r) {
            tree[p].sum=tree[p].dat=tree[p].lmax=tree[p].rmax=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
        tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
        tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
    //  tree[p].dat=max(tree[p<<1].dat,tree[p<<1|1].dat);
        tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
    }
    void change(int p,int x,int v) {
        if(tree[p].l==tree[p].r) {
            tree[p].sum=tree[p].dat=tree[p].lmax=tree[p].rmax=v;
            return;
        }
        int mid=(tree[p].l+tree[p].r)>>1;
        if(x<=mid) change(p<<1,x,v);
        else change(p<<1|1,x,v);
        tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
        tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
        tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
        tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
    }
    node ask(int p,int l,int r) {
        if(l<=tree[p].l&&r>=tree[p].r) {
            return tree[p];
        }
        int mid=(tree[p].l+tree[p].r)>>1;
    //  int val=-INF;
        node a,b,c;
        if(r<=mid) return ask(p<<1,l,r);
        if(l>=mid+1) return ask(p<<1|1,l,r);
        else{
            a=ask(p<<1,l,r);
        b=ask(p<<1|1,l,r);
        c.sum=a.sum+b.sum;
        c.lmax=max(a.lmax,a.sum+b.lmax);
        c.rmax=max(b.rmax,b.sum+a.rmax);
        c.dat=max(a.dat,max(b.dat,a.rmax+b.lmax));
        return c;
        }
    }
    int main() {
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=1; i<=n; i++) {
            cin>>a[i];
        }
        build(1,1,n);
        int x,y,z;
        while(m--)
        {
            cin>>x>>y>>z;
    //      if(y>z) swap(y,z); //不能在这里swap 会影响命令2 
            if(x==1)cout<<ask(1,min(y,z),max(y,z)).dat<<endl;
            else change(1,y,z);
        }
        return 0;
    }
    #endif
    
    
  • 1

信息

难度
8
分类
(无)
标签
(无)
递交数
19
已通过
5
通过率
26%
上传者