第一次写二维线段树写炸了。。
查看原帖
第一次写二维线段树写炸了。。
177069
李白莘莘学子楼主2020/6/2 17:25

搞了2天硬是没找到错在哪。。

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1007
#define ll ((now<<2)+1)
//左上角 
#define lr ((now<<2)+2)
//右上角 
#define rl ((now<<2)+3)
//左下角 
#define rr ((now<<2)+4)
//右下角 
#define midx ((lx+rx)>>1)
#define midy ((ly+ry)>>1)
using namespace std;
inline int read()
{
    int ans=0;
    char ch=getchar(),last=' ';
    while(ch<'0'||ch>'9')last=ch,ch=getchar();
    while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
    return last=='-'?-ans:ans;
}
int n,d1,s,tree[N*16],lzt[N*16],a,b,c,d,e;
void build(int lx,int rx,int ly,int ry,int now)
{
    if(lx==rx&&ly==ry)
    {
        tree[now]=0;
        return;
    }
    build(lx,midx,ly,midy,ll);
    tree[now]=max(tree[now],tree[ll]);
    if(ly!=ry)
    {
        build(lx,midx,midy+1,ry,lr);
        tree[now]=max(tree[now],tree[lr]);
    }
    if(lx!=rx)
    {
        build(midx+1,rx,ly,ry,rl);
        tree[now]=max(tree[now],tree[rl]);
    }
    if(ly!=ry&&lx!=rx)
    {
        build(midx+1,rx,midy+1,ry,rr);
        tree[now]=max(tree[now],tree[rr]);
    }
    return;
}
void pushdown(int lx,int rx,int ly,int ry,int now)
{
    tree[ll]=lzt[now];
    lzt[ll]=lzt[now];
    if(ly!=ry)
    {
        tree[lr]=lzt[now];
        lzt[lr]=lzt[now];
    }
    if(lx!=rx)
    {
        tree[rl]=lzt[now];
        lzt[rl]=lzt[now];
    }
    if(ly!=ry&&lx!=rx)
    {
        tree[rr]=lzt[now];
        lzt[rr]=lzt[now];
    }
    lzt[now]=0;
    return;
}
void update(int lx,int rx,int ly,int ry,int qlx,int qrx,int qly,int qry,int now,int mx)
{
    if(lx>=qlx&&rx<=qrx&&ly>=qly&&ry<=qry)
    {
        tree[now]=mx;
        lzt[now]=mx;
        return;
    }
    pushdown(lx,rx,ly,ry,now);
    if(qlx<=midx&&qly<=midy)
    {
        update(lx,midx,ly,midy,qlx,qrx,qly,qry,ll,mx);
        tree[now]=max(tree[now],tree[ll]);
    }
    if(qlx<=midx&&qry>midy&&ly!=ry)
    {
        update(lx,midx,midy+1,ry,qlx,qrx,qly,qry,lr,mx);
        tree[now]=max(tree[now],tree[lr]);
    }
    if(qrx>midx&&qly<=midy&&lx!=rx)
    {
        update(midx+1,rx,ly,midy,qlx,qrx,qly,qry,rl,mx);
        tree[now]=max(tree[now],tree[rl]);
    }
    if(qrx>midx&&qry>midy&&ly!=ry&&lx!=rx)
    {
        update(midx+1,rx,midy+1,ry,qlx,qrx,qly,qry,rr,mx);
        tree[now]=max(tree[now],tree[rr]);
    }
    return;
}
int query(int lx,int rx,int ly,int ry,int qlx,int qrx,int qly,int qry,int now)
{
    int maxx=-1;
    if(lx>=qlx&&rx<=qrx&&ly>=qly&&ry<=qry)
        return tree[now];
    pushdown(lx,rx,ly,ry,now);
    if(qlx<=midx&&qly<=midy)
    {
        maxx=max(maxx,query(lx,midx,ly,midy,qlx,qly,qrx,qry,ll));
    }
    if(qlx<=midx&&qry>midy&&ly!=ry)
    {
        maxx=max(maxx,query(lx,midx,midy+1,ry,qlx,qly,qrx,qry,lr));
    }
    if(qrx>midx&&qly<=midy&&lx!=rx)
    {
        maxx=max(maxx,query(midx+1,rx,ly,midy,qlx,qly,qrx,qry,rl));
    }
    if(qrx>midx&&qry>midy&&ly!=ry&&lx!=rx)
    {
        maxx=max(maxx,query(midx+1,rx,midy+1,ry,qlx,qly,qrx,qry,rr));
    }
    return maxx;
}
int main(){
    d1=read(),s=read(),n=read();
	build(1,d1,1,s,0);
    for(int i=1;i<=n;i++)
    {
        a=read(),b=read(),c=read(),d=read(),e=read();
        int sum=query(1,d1,1,s,d+1,d+a,e+1,e+b,0);
        sum+=c;
        update(1,d1,1,s,d+1,d+a,e+1,e+b,0,sum);
 /*       printf("i=%d\n",i);
        for(int k=1;k<=d1;k++)
        {
        	for(int j=1;j<=s;j++)
        		printf("%d ",query(1,d1,1,s,k,k,j,j,0));
        	cout<<endl;
//自检代码
            */
		}
    }
    printf("%d\n",query(1,d1,1,s,1,d1,1,s,0));
    return 0;
}

希望julao们指教

2020/6/2 17:25
加载中...