|
|
Posted on 2010-10-29 14:01 acronix 阅读(449) 评论(0) 编辑 收藏 引用 所属分类: hzshuai解题报告 、 hzshuai收集的模板
题意就不多说了。 分析：就是把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;
}
|