搞了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们指教