> 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;
> }

• 我一维线段树n*2*15的空间都超，你那个k*n*n的空间是不可能过的 (0) cycpp 2009-09-22 21:13:14