疯狂二分的二维线段树哪里错了，没找出来
#include <bits/stdc++.h>#define maxn 1001
#define son1 rt<<2 //左上
#define son2 rt<<2|1//左下
#define son3 rt<<2|2//右上
#define son4 rt<<2|3//右下
#define midl ((l+r)/2)
#define midh ((u+d)/2)
using namespace std;
int a;
struct node{
int sum;
int lazy;
};
node tree[(maxn<<2)*(maxn<<2)];
int mergetree(node a,node b,node c,node d){
int res;
res=a.sum+b.sum+c.sum+d.sum;
return res;
}
void pushdown(int rt,int l,int r,int u,int d){
if(tree.lazy){
if(l!=r&&u==d){
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(midl-l+1);
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(r-midl);
return;
}
if(l==r&&u!=d){
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(midh-u+1);
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(d-midh);
return;
}
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(midl-l+1)*(midh-u+1);
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(r-midl)*(midh-u+1);
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(r-midl)*(d-midh);
tree.lazy+=tree.lazy;
tree.sum+=tree.lazy*(d-midh)*(midl-l+1);
tree.lazy=0;
}
}
void buildtree(int rt,int l,int r,int u,int d){
tree.lazy=0;
if(l==r&&u==d){
tree.sum=a;
return;
}
if(l!=r&&u==d){
buildtree(son1,l,midl,u,u);
buildtree(son3,midl+1,r,u,u);
tree.sum=tree.sum=0;
tree.lazy=tree.lazy=0;
tree.sum=mergetree(tree,tree,tree,tree);
return;
}
if(l==r&&u!=d){
buildtree(son1,l,l,u,midh);
buildtree(son2,l,l,midh+1,d);
tree.sum=tree.sum=0;
tree.lazy=tree.lazy=0;
tree.sum=mergetree(tree,tree,tree,tree);
return;
}
buildtree(son1,l,midl,u,midh); //左上
buildtree(son2,l,midl,midh+1,d); //左下
buildtree(son3,midl+1,r,u,midh);//右上
buildtree(son4,midl+1,r,midh+1,d);//右下
tree.sum=mergetree(tree,tree,tree,tree);
return;
}
void update(int rt,int l,int r,int u,int d,int ql,int qr,int qu,int qd,int v){
if(l<=ql&&qr<=r&&u<=qu&&qd<=d){
tree.sum+=v;
tree.lazy=v;
return;
}
if(r<ql||l>qr||d<qu||u>qd){
return;
}
if(l!=r&&u==d){
update(son1,l,midl,u,u,ql,qr,qu,qd,v);
update(son3,midl+1,r,u,u,ql,qr,qu,qd,v);
tree.sum=mergetree(tree,tree,tree,tree);
return;
}
if(l==r&&u!=d){
update(son1,l,l,u,midh,ql,qr,qu,qd,v);
update(son2,l,l,midh+1,d,ql,qr,qu,qd,v);
tree.sum=mergetree(tree,tree,tree,tree);
return;
}
pushdown(rt,l,r,u,d);
update(son1,l,midl,u,midh,ql,qr,qu,qd,v); //左上
update(son2,l,midl,midh+1,d,ql,qr,qu,qd,v); //左下
update(son3,midl+1,r,u,midh,ql,qr,qu,qd,v);//右上
update(son4,midl+1,r,midh+1,d,ql,qr,qu,qd,v);//右下
tree.sum=mergetree(tree,tree,tree,tree);
return;
}
int query(int rt,int l,int r,int u,int d,int ql,int qr,int qu,int qd){
if(l<=ql&&qr<=r&&u<=qu&&qd<=d){
return tree.sum;
}
pushdown(rt,l,r,u,d);
if(r<ql||l>qr||d<qu||u>qd){
return 0;
}
if(l!=r&&u==d){
return query(son1,l,midl,u,u,ql,qr,qu,qd)+query(son3,midl+1,r,u,u,ql,qr,qu,qd);
}
if(l==r&&u!=d){
returnquery(son1,l,l,u,midh,ql,qr,qu,qd)+ query(son2,l,l,midh+1,d,ql,qr,qu,qd);
}
returnquery(son1,l,midl,u,midh,ql,qr,qu,qd)+query(son2,l,midl,midh+1,d,ql,qr,qu,qd)+query(son3,midl+1,r,u,midh,ql,qr,qu,qd)+query(son4,midl+1,r,midh+1,d,ql,qr,qu,qd);
}
int main(){
int t;
cin>>t;
memset(a,1,sizeof(a));
while(t--){
buildtree(1,1,1000,1,1000);
printf("%d\n",query(1,1,1000,1,1000,1,1000,1,1000));
}
return 0;
}
抱歉了兄弟，你的代码有点乱，我猜原因应该是出现在数组长度上，如有误，请见谅：
你的代码数组结构体长度为 (maxn<<2)*(maxn<<2) = 4004*4004 = 16032016（<<2 如同 *4）
而你的数组 int a; 长度为 1001*1001 = 1002001 显然不足（第 52 行中的 tree.sum = a，不足的部份）
运行代码无论输入什么值都只会出现：-1852734912
顶一下 {:10_249:} 顶顶帖子{:10_257:} 好典的错误写法
页:
[1]