posts - 64, comments - 4, trackbacks - 0, articles - 0

题意就不多说了。

分析:就是把poj1177简单改动就行了。

总结:出错时输出看看prelen对不对就行了。




#include <cstdio>
#include 
<stdlib.h>
#include 
<algorithm>
using namespace std;

const int root = 0
;

struct
 Node{
       
int
 l,r,cover;
       
int
 cnt,len;
       
int
 lf,rf;
       
int
 lnd,rnd;
}node[
200010
];
int
 cnt,cnty;
int indx[80010
];

struct
 Line{
       
int
 x,y1,y2;
       
bool
 f;
} line[
80010
];

void Creat(int p ,int l,int
 r)
{
     node[p].l 
= l; node[p].r =
 r;
     node[p].len 
= node[p].cnt = node[p].cover = 0
;
     node[p].lf 
= node[p].rf = 0
;
     
if(r - l > 1
)
     {
          
int mid = (l + r) >> 1
;
          node[p].lnd 
= ++
cnt;
          Creat(cnt,l,mid);
          node[p].rnd 
= ++
cnt;
          Creat(cnt,mid,r);
     }
     
else {node[p].lnd = -1; node[p].rnd = -1
;}
}

void upData(int
 p)
{
     
if (node[p].cover > 0
)
     {
         node[p].len 
= indx[node[p].r] -
 indx[node[p].l];
         node[p].cnt 
= 1
;
         node[p].lf 
= node[p].rf = 1
;
     }
     
else if (node[p].l == node[p].r -1
)
          {
             node[p].cover 
= 0
;
             node[p].len 
= 0
;
             node[p].lf 
= node[p].rf = node[p].cnt = 0
;
          }
          
else
 {
                
int left =
 node[p].lnd;
                
int right =
 node[p].rnd;
                node[p].len 
= node[left].len +
 node[right].len;
                node[p].lf 
=
 node[left].lf;
                node[p].rf 
=
 node[right].rf;
                node[p].cnt 
= node[left].cnt + node[right].cnt - node[left].rf*
node[right].lf;
               }
}

void Insert(int p,int l,int
 r)
{
     
if(l <= node[p].l && node[p].r <=
 r)
          node[p].cover 
++
;
     
else
 {
            
int mid = (node[p].l + node[p].r) >> 1
;
            
if(mid >
 l)
                   Insert(node[p].lnd,l,r);
            
if (mid <
 r)
               Insert(node[p].rnd,l,r);
          }
     upData(p);
}

void Delete(int p,int l,int
 r)
{
     
if(l <= node[p].l && node[p].r <=
 r)
          node[p].cover
--
;
     
else
 {
             
int mid = (node[p].l + node[p].r) >> 1
;
             
if(mid >
 l)
                    Delete(node[p].lnd,l,r);
             
if (mid <
 r)
                Delete(node[p].rnd,l,r);
          }
     upData(p);
}

bool cmp(const Line &a,const Line &
b)
{
    
return a.x <
 b.x;
}

int Bi_Search(int key)//二分查找 

{
    
int l = 1,r = cnty+1
,mid;
    
while (l <
 r)
    {
          mid 
= (l + r) >> 1
;
          
if(indx[mid] ==
 key)
              
return
 mid;
          
else if(indx[mid] <
 key)
                  l  
= mid + 1
;
               
else r =
 mid; 
    }
}

void Init_Index()//离散化(排序= 去重 

{
    sort(indx
+1,indx+1+
cnty);
    
int m = 1
;
    
for (int i = 2; i <= cnty; i++
)
        
if(indx[i] != indx[i-1
])
        {
           m
++
;
           indx[m] 
=
 indx[i];
        }
    cnty 
=
 m;
}

int
 main()
{
    
int
 n,i,j;
    
long long
 ans;
    
int
 x,y,h,prelen,left,right;
    
while (scanf("%d",&n) !=
 EOF)
    {
          cnty 
= 1
;
          indx[cnty] 
= 0
;
          
for (i = 1; i <= n+n; i+=2
)
          {
              scanf(
"%d %d %d",&x,&y,&
h);
              line[i].x 
= x; line[i].y1 = 0; line[i].y2 =
 h; 
              line[i].f 
= true
;
              line[i
+1].x = y; line[i+1].y1= 0; line[i+1].y2 =
 h; 
              line[i
+1].f = false
;
              indx[
++cnty] =
 h;
          }
          sort(line
+1,line+1+n+
n,cmp);
          Init_Index();
          cnt 
= 0
;
          Creat(root,
1
,cnty);
          left 
= 1
;
          right 
= Bi_Search(line[1
].y2);
          Insert(root,left,right);
          prelen 
=
 node[root].len;
          ans 
= 0
;
          
//printf("1.len = %d\n",prelen);

          for (i = 2; i <= n+n; i++)
          {
              left  
= 1
;
              right 
=
 Bi_Search(line[i].y2);
              
              
if
 (line[i].f)
                 Insert(root,left,right);
              
else
 Delete(root,left,right);
              
              
//注意 long long 

              ans += (long long)prelen*((long long)line[i].x - (long long)line[i-1].x);
              prelen 
=
 node[root].len; 
              
/****************检查出错很好的手段************************/

              
//printf("i = %d.len = %d\n",i,prelen); 
          }
          printf(
"%I64d\n"
,ans);
    }
    
return 0
;
}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理