疯狂二分的二维线段树哪里错了，没找出来

3w.com

#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[1001][1001];
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[rt].lazy){
        if(l!=r&&u==d){
            tree[son1].lazy+=tree[rt].lazy;
            tree[son1].sum+=tree[rt].lazy*(midl-l+1);
            tree[son3].lazy+=tree[rt].lazy;
            tree[son3].sum+=tree[rt].lazy*(r-midl);
            return;
        }
        if(l==r&&u!=d){
            tree[son1].lazy+=tree[rt].lazy;
            tree[son1].sum+=tree[rt].lazy*(midh-u+1);
            tree[son2].lazy+=tree[rt].lazy;
            tree[son2].sum+=tree[rt].lazy*(d-midh);
            return;
        }
        tree[son1].lazy+=tree[rt].lazy;
        tree[son1].sum+=tree[rt].lazy*(midl-l+1)*(midh-u+1);
        tree[son3].lazy+=tree[rt].lazy;
        tree[son3].sum+=tree[rt].lazy*(r-midl)*(midh-u+1);
        tree[son4].lazy+=tree[rt].lazy;
        tree[son4].sum+=tree[rt].lazy*(r-midl)*(d-midh);
        tree[son2].lazy+=tree[rt].lazy;
        tree[son2].sum+=tree[rt].lazy*(d-midh)*(midl-l+1);
        tree[rt].lazy=0;
    }
  
}
void buildtree(int rt,int l,int r,int u,int d){
    tree[rt].lazy=0;
    if(l==r&&u==d){
        tree[rt].sum=a[l][u];
        return;
    }
    if(l!=r&&u==d){
        buildtree(son1,l,midl,u,u);
        buildtree(son3,midl+1,r,u,u);
        tree[son2].sum=tree[son4].sum=0;
        tree[son2].lazy=tree[son4].lazy=0;
        tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        return;
    }
    if(l==r&&u!=d){
        buildtree(son1,l,l,u,midh);
        buildtree(son2,l,l,midh+1,d);
        tree[son3].sum=tree[son4].sum=0;
        tree[son3].lazy=tree[son4].lazy=0;
        tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        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[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
    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[rt].sum+=v;
        tree[rt].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[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        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[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        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[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
    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[rt].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){
        return  query(son1,l,l,u,midh,ql,qr,qu,qd)+ query(son2,l,l,midh+1,d,ql,qr,qu,qd);
    }
   
    return  query(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]; 长度为 1001*1001 = 1002001 显然不足（第 52 行中的 tree[rt].sum = a[l][u]，不足的部份）
运行代码无论输入什么值都只会出现：-1852734912

心驰神往

顶一下

Passepartout

jzhjedi

顶顶帖子