zoj 3245
zoj网络赛farming那道题，第一次写四分树，哪里有问题吗，或者这种方法有问题？ 
提交一直RE 
#include <iostream>
using namespace std;
//动态四分树 
typedef long long Int64;
struct node{
       node *n1,*n2,*n3,*n4;
       int ma,xl,xr,yt,yb;
       int full;
}no[201000];

int nocnt;
//申请节点编号，测试用 
int k(){
	if(nocnt==201000){ while(1); }
    else {
        nocnt++;
        return nocnt-1;
    }
}       
//将叶节点四分 
void co(node *now){
    int xmid=(now->xl+now->xr)/2;
    int ymid=(now->yt+now->yb)/2;
    now->n1=&no[k()];
    now->n2=&no[k()];
    now->n3=&no[k()];
    now->n4=&no[k()];
    now->n1->full=1;
    now->n1->ma=now->ma;
    now->n2->full=1;
    now->n2->ma=now->ma;
    now->n3->full=1;
    now->n3->ma=now->ma;
    now->n4->full=1;
    now->n4->ma=now->ma;
    now->n1->xl=now->n3->xl=now->xl;
    now->n1->yt=now->n2->yt=now->yt;
    now->n2->xr=now->n4->xr=now->xr;
    now->n3->yb=now->n4->yb=now->yb;
    now->n1->xr=now->n3->xr=now->n2->xl=now->n4->xl=xmid;
    now->n1->yb=now->n2->yb=now->n3->yt=now->n4->yt=ymid;
    now->n1->n1=now->n2->n1=now->n3->n1=now->n4->n1=NULL;
    return ;
}
//修改，记录最值 
void mod(node *now,int xl,int xr,int yt,int yb,int k){
    if(xl<now->xl||xr>now->xr||yt<now->yt||yb>now->yb)while(1);
    int xmid=(now->xl+now->xr)/2;
    int ymid=(now->yt+now->yb)/2;
    if(xl==now->xl&&xr==now->xr&&yt==now->yt&&yb==now->yb){
        if(now->full==1){
            if(now->ma<k)now->ma=k;
        }
        
		else {
            mod(now->n1,xl,xmid,yt,ymid,k);
            mod(now->n2,xmid,xr,yt,ymid,k);
            mod(now->n3,xl,xmid,ymid,yb,k);
            mod(now->n4,xmid,xr,ymid,yb,k);
        }   
    }
    else {
        if(now->full==1){
            now->full=0;
            co(now);
        }
        if(xl<xmid&&yt<ymid){
            if(xr>xmid&&yb>ymid){
                mod(now->n1,xl,xmid,yt,ymid,k);
                mod(now->n2,xmid,xr,yt,ymid,k);
                mod(now->n3,xl,xmid,ymid,yb,k);
                mod(now->n4,xmid,xr,ymid,yb,k);
            }
            if(xr<=xmid&&yb>ymid){
                mod(now->n1,xl,xr,yt,ymid,k);
                mod(now->n3,xl,xr,ymid,yb,k);
            }
            if(xr>xmid&&yb<=ymid){
                mod(now->n1,xl,xmid,yt,yb,k);
                mod(now->n2,xmid,xr,yt,yb,k);
            }
            if(xr<=xmid&&yb<=ymid){
                mod(now->n1,xl,xr,yt,yb,k);
            }
        }
        else if(xl>=xmid&&yt<ymid){
            if(yb>ymid){
                mod(now->n2,xl,xr,yt,ymid,k);
                mod(now->n4,xl,xr,ymid,yb,k);
            }
            else {
                mod(now->n2,xl,xr,yt,yb,k);
            }
        }
        else if(xl<xmid&&yt>=ymid){
            if(xr>xmid){
                mod(now->n3,xl,xmid,yt,yb,k);
                mod(now->n4,xmid,xr,yt,yb,k);
            }
            else {
                mod(now->n3,xl,xr,yt,yb,k);
            }
        }
        else if(xl>=xmid&&yt>=ymid){
            mod(now->n4,xl,xr,yt,yb,k);
        }  
    }
    return ;
}
//计算结果 
Int64 cal(node *now){
    if(now->full==1){
        return (Int64)(now->xr-now->xl)*(Int64)(now->yb-now->yt)*now->ma;
    }
    else return (Int64)(cal(now->n1)+cal(now->n2)+(Int64)cal(now->n3)+cal(now->n4));
}
int main(){
    int cas,n,m,i,a[5],j,xl,xr,yt,yb,ca=1;
    cin>>cas;
    while(cas--){
        nocnt=0;
        cin>>n>>m;
        node *root=&no[k()];
        root->ma=0;
        root->full=1;
        root->n1=NULL;
        root->xl=0;
        root->xr=1<<21;
        root->yt=0;
        root->yb=1<<21;
        for(i=1;i<=n;i++)cin>>a[i];
        for(i=0;i<m;i++){
            cin>>xl>>yt>>xr>>yb>>j;
            mod(root,xl+(1<<20),xr+(1<<20),yt+(1<<20),yb+(1<<20),a[j]);
        }
		cout<<"Case "<<ca++<<": "<< cal(root)<<endl;
        //printf("Case %d: %d\n",ca++,cal(root));
    }
    return 0;
}

• up (4238) insotc 2009-09-15 23:15:06
  • 我一维线段树n*2*15的空间都超，你那个k*n*n的空间是不可能过的 (0) cycpp 2009-09-22 21:13:14
• up (4238) insotc 2009-09-17 22:04:45
• up (4238) wanglinggui 2009-09-21 11:58:54
  • Re:四分树内存能吃消不？ (0) Syd 2009-09-21 13:17:32
    • 这个算是静态的吗？ (0) wanglinggui 2009-09-21 14:05:44
• Re:求教，网络赛farming题，这个四分树有问题吗？ (18) mabaochang 2009-09-21 15:49:29
  • 是啊 我想知道这个为什么re (22) wanglinggui 2009-09-21 16:11:31
    • Re:是啊 我想知道这个为什么re (2) acm_newer 2009-09-21 19:00:08