[ACM] POJ 3277 City Horizon 解题报告, 线段树+离散化

145 Replies

第一道线段树.. 略难。 引用忘了哪看的一句话“10亿的的数据规模是任何数据结构都无能为力的，所以必须离散化”。因为略复杂我用class写的…yzhw牛说“线段树编程复杂度太高，一般用树狀数组或者STL set。不要class，class运行爆慢” 但是哥就是用class和链表过了，怎样！！ 1200ms.. 不过后来看了一下Google到用Pascal的蒟蒻牛的代码，发现树狀数组果然好用！

hw给了我篇论文，我发现现在的程度知道了一个数据结构的意思&&一些优化比如“lazy”，写出来的东西details上面大家都差不多的。比如这道题目的lazy我也是加了个-1作标签说明下面的节点需要递归确认，即这一块不是一大块一样的

优化有二：
1. compress()  每次插入完一个building以后沿着树往下看有没有标记为-1但是左右子树height（toLoad）相等的，如果有合并左右子树。实践证明这个优化对这题的数据用处不大，反而拖到了1800ms…
2. 这个厉害了，没它我算5000的数据都要跑半分钟，而还有两组40000的数据，加了这优化4w的秒出。也是刚刚那篇里提到的“观察发现，线段树的建树、统计操作已难以再优化，但插入操作却任可以优化。由于一开始房子的高度无序，所以每次插入如果全部包含不能直接赋值，还需要向下递归左右子树。其实我们可以先将房子的高度排序，然后再依次插入，这样一旦全部包含就可以直接赋值，程序的效率大大提高。这样这道题就可以AC了。”

代码：

[cpp]#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

struct Building {
int s,e,h;
};

int searchMap(int map[],int mapN,int value) {
int p0=0,p1=mapN-1;
while(p0<p1) {
int mid=(p0+p1)/2;
if(value==map[mid])
p0=p1=mid;
if(value<map[mid])
p1=mid-1;
if(value>map[mid])
p0=mid+1;
}
return p0;
}

class segmentTreeNode {
public:
int p0,p1;
int toLoad;
int mid() {
return (p0+p1)/2;
}
segmentTreeNode *lChild,*rChild,*parent;
segmentTreeNode(int p0__,int p1__) {
toLoad=0;
p0=p0__;
p1=p1__;
if(p0==p1-1)
lChild=rChild=NULL;
else {
lChild=new segmentTreeNode(p0,mid());
lChild->parent=this;
rChild=new segmentTreeNode(mid(),p1);
rChild->parent=this;
}
}
~segmentTreeNode() {
delete lChild;
delete rChild;
}
void load(const int,const int,const int);
void compress();
long long result(int map[]);
};

void segmentTreeNode::load(const int p0__,const int p1__,const int height) {
if(toLoad>=height)
return;
if(p0__==p0 && p1__==p1) {
toLoad=height;
return;
}
if(toLoad>=0) {
lChild->toLoad=toLoad;
rChild->toLoad=toLoad;
}
toLoad=-1;
if(p0__<mid()) {
int end=min(p1__,mid());
lChild->load(p0__,end,height);
}
if(p1__>mid()) {
int start=max(p0__,mid());
rChild->load(start,p1__,height);
}
return;
}

void segmentTreeNode::compress() {
if(toLoad==-1) {
lChild->compress();
rChild->compress();
if(lChild->toLoad!=-1 && lChild->toLoad==rChild->toLoad)
toLoad=lChild->toLoad;
}
}

long long segmentTreeNode::result(int map[]) {
if(toLoad>=0)
return ((long long)map[p1]-map[p0])*toLoad;
return lChild->result(map)+rChild->result(map);
}

int comp(const void *a,const void *b) {
return *(int *)a-*(int *)b;
}

int comp2(const void *__a,const void *__b) {
Building *a=(Building *)__a;
Building *b=(Building *)__b;
return a->h-b->h;
}

int main() {
Building building[40000];
int buildingN;
scanf("%d",&buildingN);
int map[80000];
for(int i=0;i<buildingN;i++) {
scanf("%d%d%d",&building[i].s,&building[i].e,&building[i].h);
map[2*i]=building[i].s;
map[2*i+1]=building[i].e;
}

qsort(map,2*buildingN,sizeof(int),comp);

int p0=0,p1=0;
while(p1<2*buildingN) {
if(map[p1]==map[p0]) {
p1++;
continue;
}
map[++p0]=map[p1];
p1++;
}
int mapN=p0+1;

segmentTreeNode tree(0,mapN-1);
tree.parent=NULL;

qsort(building,buildingN,sizeof(Building),comp2);

for(int i=0;i<buildingN;i++) {
int start=searchMap(map,mapN,building[i].s);
int end=searchMap(map,mapN,building[i].e);
int height=building[i].h;
tree.load(start,end,height);
//tree.compress();
}

printf("%lld\n",tree.result(map));

return 0;
}[/cpp]

145 thoughts on “[ACM] POJ 3277 City Horizon 解题报告, 线段树+离散化”

Leave a Reply

Your email address will not be published. Required fields are marked *