头像

ACwisher


访客:95

离线:11小时前



ACwisher
13天前

题目链接 Uva 11992

输入到第一个操作时程序就崩溃了。代码实在太长了,希望有dalao能帮我一块儿查一下。
之前直接开二维本地已经过了,但是实际上会炸空间,所以交上去RE,所以调整成了一维。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,inf=1e9+7;
int r1,c1,m;
struct pos{
    int l,r,sum,add,change,mx,mn;
}tree[N<<2];
void pushup(int rt,int p){
    tree[(p-1)*c1+rt].sum=tree[(p-1)*c1+rt<<1].sum+tree[(p-1)*c1+rt<<1|1].sum;
    tree[(p-1)*c1+rt].mx=max(tree[(p-1)*c1+rt<<1].mx,tree[(p-1)*c1+rt<<1|1].mx);
    tree[(p-1)*c1+rt].mn=min(tree[(p-1)*c1+rt<<1].mn,tree[(p-1)*c1+rt<<1|1].mn);
}
void build(int rt,int l,int r,int p){
    tree[(p-1)*c1+rt].l=l;tree[(p-1)*c1+rt].r=r;tree[(p-1)*c1+rt].change=-1;
    tree[(p-1)*c1+rt].mn=tree[(p-1)*c1+rt].mx=tree[(p-1)*c1+rt].sum=tree[(p-1)*c1+rt].add=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(rt<<1,l,mid,p);
    build(rt<<1|1,mid+1,r,p);
    pushup(rt,p);
}
void pushdown(int rt,int p){
    if(tree[(p-1)*c1+rt].change>=0){
        tree[(p-1)*c1+rt<<1].add=0;
        tree[(p-1)*c1+rt<<1].change=tree[(p-1)*c1+rt].change;
        tree[(p-1)*c1+rt<<1].sum=tree[(p-1)*c1+rt].change*(tree[(p-1)*c1+rt<<1].r-tree[(p-1)*c1+rt<<1].l+1);
        tree[(p-1)*c1+rt<<1].mn=tree[(p-1)*c1+rt<<1].mx=tree[(p-1)*c1+rt<<1].change;

        tree[(p-1)*c1+rt<<1|1].add=0;
        tree[(p-1)*c1+rt<<1|1].change=tree[(p-1)*c1+rt].change;
        tree[(p-1)*c1+rt<<1|1].sum=tree[(p-1)*c1+rt].change*(tree[(p-1)*c1+rt<<1|1].r-tree[(p-1)*c1+rt<<1|1].l+1);
        tree[(p-1)*c1+rt<<1|1].mn=tree[(p-1)*c1+rt<<1|1].mx=tree[(p-1)*c1+rt<<1|1].change;

        tree[(p-1)*c1+rt].change=-1;
    }
    if(tree[(p-1)*c1+rt].add>0){
        tree[(p-1)*c1+rt<<1].add+=tree[(p-1)*c1+rt].add;
        tree[(p-1)*c1+rt<<1].sum+=tree[(p-1)*c1+rt].add*(tree[(p-1)*c1+rt<<1].r-tree[(p-1)*c1+rt<<1].l+1);
        tree[(p-1)*c1+rt<<1].mn+=tree[(p-1)*c1+rt].add;
        tree[(p-1)*c1+rt<<1].mx+=tree[(p-1)*c1+rt].add;

        tree[(p-1)*c1+rt<<1|1].add+=tree[(p-1)*c1+rt].add;
        tree[(p-1)*c1+rt<<1|1].sum+=tree[(p-1)*c1+rt].add*(tree[(p-1)*c1+rt<<1|1].r-tree[(p-1)*c1+rt<<1|1].l+1);
        tree[(p-1)*c1+rt<<1|1].mn+=tree[(p-1)*c1+rt].add;
        tree[(p-1)*c1+rt<<1|1].mx+=tree[(p-1)*c1+rt].add;

        tree[(p-1)*c1+rt].add=0;
    }
}
void update(int rt,int L,int R,int val,int p){
    if(L<=tree[(p-1)*c1+rt].l&&tree[(p-1)*c1+rt].r<=R){
        tree[(p-1)*c1+rt].add+=val;
        tree[(p-1)*c1+rt].sum+=val*(tree[(p-1)*c1+rt].r-tree[(p-1)*c1+rt].l+1);
        tree[(p-1)*c1+rt].mn+=val;
        tree[(p-1)*c1+rt].mx+=val;
        return;
    }
    pushdown(rt,p);
    int mid=(tree[(p-1)*c1+rt].l+tree[(p-1)*c1+rt].r)>>1;
    if(L<=mid) update(rt<<1,L,R,val,p);
    if(R>mid) update(rt<<1|1,L,R,val,p);
    pushup(rt,p);
    return;
}
void update2(int rt,int L,int R,int val,int p){
    if(L<=tree[(p-1)*c1+rt].l&&tree[(p-1)*c1+rt].r<=R){
        tree[(p-1)*c1+rt].change=val;
        tree[(p-1)*c1+rt].sum=val*(tree[(p-1)*c1+rt].r-tree[(p-1)*c1+rt].l+1);
        tree[(p-1)*c1+rt].add=0;
        tree[(p-1)*c1+rt].mn=val;
        tree[(p-1)*c1+rt].mx=val;
        return;
    }
    pushdown(rt,p);
    int mid=(tree[(p-1)*c1+rt].l+tree[(p-1)*c1+rt].r)>>1;
    if(L<=mid) update2(rt<<1,L,R,val,p);
    if(R>mid) update2(rt<<1|1,L,R,val,p);
    pushup(rt,p);
    return;
}
pos query(int rt,int L,int R,int p){
    pos ret,tmp;
    ret.mn=inf;ret.mx=ret.sum=0;
    if(L<=tree[(p-1)*c1+rt].l&&tree[(p-1)*c1+rt].r<=R) return tree[(p-1)*c1+rt];
    pushdown(rt,p);
    int mid=(tree[(p-1)*c1+rt].l+tree[(p-1)*c1+rt].r)>>1;
    if(L<=mid){
        tmp=query(rt<<1,L,R,p);
        ret.mn=min(ret.mn,tmp.mn);
        ret.mx=max(ret.mx,tmp.mx);
        ret.sum+=tmp.sum;;
    }
    if(R>mid){
        tmp=query(rt<<1|1,L,R,p);
        ret.mn=min(ret.mn,tmp.mn);
        ret.mx=max(ret.mx,tmp.mx);
        ret.sum+=tmp.sum;
    }
    return ret;
}
int main(){
    while(scanf("%d%d%d",&r1,&c1,&m)==3){
        for(int i=1;i<=r1;i++) build(1,1,c1,i);
        while(m--){
            int opt,xa,xb,ya,yb,v;
            scanf("%d%d%d%d%d",&opt,&xa,&ya,&xb,&yb);
            if(opt==1){
                scanf("%d",&v);
                for(int i=xa;i<=xb;i++) update(1,ya,yb,v,i);
            } else if(opt==2){
                scanf("%d",&v);
                for(int i=xa;i<=xb;i++) update2(1,ya,yb,v,i);
            } else {
                pos ret;ret.mn=inf;ret.mx=ret.sum=0;
                for(int i=xa;i<=xb;i++){
                    pos qaq=query(1,ya,yb,i); 
                    ret.mn=min(ret.mn,qaq.mn);
                    ret.mx=max(ret.mx,qaq.mx);
                    ret.sum+=qaq.sum;
                }
                printf("%d %d %d\n",ret.sum,ret.mn,ret.mx);
            }
        }
    }
    return 0;
} 



ACwisher
14天前

题目描述

单点修改,区间查询,求最大子段和

样例

input

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

output

2
-1

线段树

算法

lans,该区间内前缀和最大值
rans,后缀和最大值
ans,最大子段和
sum,区间和

update:
lans:左儿子lans 或 左儿子sum+右儿子lans
rans同理
ans是 左儿子ans 或 右儿子ans 或左儿子rans+右儿子lans
sum直接左右儿子相加

query:
1.查询区间包含在当前区间内:直接返回t[rt]
2.查询区间与右子树区间无重合:去左子树算答案
3.查询区间与左子树区间无重合 去右子树
4.其他直接像update中一般更新

备注:
这位dalao的解释也许更加清楚

时间复杂度O(mlogn)

每次操作logn(应该是吧)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,m,a[N];
struct pos{
    int l,r,ans,lans,rans,sum;
}t[N<<2];
void build(int rt,int l,int r){
//  cout<<"ee"<<rt<<" "<<l<<" "<<r<<endl;
    t[rt].l=l;t[rt].r=r;
    if(l==r){
        t[rt].lans=t[rt].rans=t[rt].ans=t[rt].sum=a[l];
        return;
    }

    int mid=(l+r)>>1; 
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);

    t[rt].ans=max(t[rt<<1].rans+t[rt<<1|1].lans,max(t[rt<<1].ans,t[rt<<1|1].ans));
    t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
    t[rt].lans=max(t[rt<<1].lans,t[rt<<1].sum+t[rt<<1|1].lans);
    t[rt].rans=max(t[rt<<1|1].rans,t[rt<<1].rans+t[rt<<1|1].sum);
    return;
}
void update(int rt,int x,int v){
    if(t[rt].l==t[rt].r){
        t[rt].lans=t[rt].rans=t[rt].ans=t[rt].sum=v;
        return;
    }

    int mid=(t[rt].l+t[rt].r)>>1; 
    if(x<=mid) update(rt<<1,x,v);
    else update(rt<<1|1,x,v);

    t[rt].ans=max(t[rt<<1].rans+t[rt<<1|1].lans,max(t[rt<<1].ans,t[rt<<1|1].ans));
    t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
    t[rt].lans=max(t[rt<<1].lans,t[rt<<1].sum+t[rt<<1|1].lans);
    t[rt].rans=max(t[rt<<1|1].rans,t[rt<<1].rans+t[rt<<1|1].sum);
}
pos query(int rt,int L,int R){
    pos qaq,tmpl,tmpr;
    if(L<=t[rt].l&&t[rt].r<=R){
    //  cout<<"ee:"<<t[rt].ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
        return t[rt];
    }

    int mid=(t[rt].l+t[rt].r)>>1;
    if(R<=mid){
    //  cout<<"ee:"<<query(rt<<1,L,R).ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
        return query(rt<<1,L,R);
    }
    if(mid<L){
    //  cout<<"ee:"<<query(rt<<1|1,L,R).ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
        return query(rt<<1|1,L,R);
    }

    //L<t[rt].l<R<t[rt].r
    tmpl=query(rt<<1,L,R);tmpr=query(rt<<1|1,L,R);
    qaq.ans=max(tmpl.rans+tmpr.lans,max(tmpl.ans,tmpr.ans));
    qaq.lans=max(tmpl.lans,tmpl.sum+tmpr.lans);
    qaq.rans=max(tmpr.rans,tmpr.sum+tmpl.rans);
    qaq.sum=tmpl.sum+tmpr.sum;
//  cout<<"ee:"<<qaq.ans<<" "<<rt<<" "<<t[rt].l<<" "<<t[rt].r<<endl;
    return qaq;
}
int main(){
    scanf("%d%d",&n,&m); 
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1){
            if(x>y) swap(x,y);
            printf("%d\n",query(1,x,y).ans);
        } else update(1,x,y);
    } 
    return 0;
}