近来忙着挑战杯的项目，还有异构编程的，没有多少时间来做题，不过偶尔也会把题目记在心里，走路吃饭睡觉的时候那么想想。有时候也会有了一些新的看法和思考，感觉这样的思考方式倒是挺安静也挺深刻的，不会拘泥于做题中对数量的追求。
还是说说线段树吧，经典题目矩形并的周长，这个问题涉及的内容还比较多，包括排序，离散化，sweep line，还有线段树。
下面是一些问题，总体思路有了，细节上遇到的一些bug
1.线段树占用的空间大小？
为何分配了3*20000的大小，却在建立一个build(1,0,20000);的大小时内存访问溢出了？
void build(int node,int begin,int end){
printf("%d %d %d\n",begin,end,node);
seg_nodes[node].set_init();
if(begin+1 == end){
return;
}
build(2*node,begin,begin+(end-begin)/2);
build(2*node+1,begin+(end-begin)/2,end);
}
注意如果要用数组保存，则要关注线段树的深度，当20000的时候，其深度可以达到与32768同样的深度
纠正：将大小seg_nodes修改成4*20000
2.insert，dele失败
原因
if(l <= begin && end <= r){
seg_nodes[node].count++;
update(node,begin,end);
return ;
}
语句忘记return；
3.我认为沿x轴方向和y轴方向的周长的计算方法是相同的。可是为何最终计算结果是错误的？
原因i++位置放错，而将x轴方向和y轴方向的周长等同处理的方法是正确的。
unsigned int sweep_line(segment array[],int size,int begin,int end){
unsigned long area = 0;
build(1,begin,end);
int current,prev;
current = prev = array[0].pos;
for(int i = 0 ; i < size ; ){
current = array[i].pos;
area += (current – prev)*seg_nodes[1].c;
while(i < size && array[i].pos == current){
i++;
if(array[i].lor == 0){
insert(1,begin,end,array[i].x,array[i].y);
}else{
dele(1,begin,end,array[i].x,array[i].y);
}
//i++ should be here.
}
prev = current;
}
return area;
}
再附上完整的代码：
#include <iostream>
#include <cstdio>
#define MAX_N 20000*4
#define debug
#undef debug
struct node_t{
int count;
int c;
bool lic;
bool ric;
void set_init(){
count = 0;
c = 0;
lic = false;
ric = false;
}
} seg_nodes[MAX_N];
int num = 0;
void build(int node,int begin,int end){
num++;
//printf("%d %d %d\n",begin,end,node);
seg_nodes[node].set_init();
if(begin+1 < end){
build(2*node,begin,begin+(end-begin)/2);
build(2*node+1,begin+(end-begin)/2,end);
}
}
void update(int node,int begin,int end){
//如果是叶子节点
if(begin+1 == end){
if(seg_nodes[node].count == 0){
seg_nodes[node].lic = false;
seg_nodes[node].ric = false;
seg_nodes[node].c = 0;
}
else{
seg_nodes[node].lic = true;
seg_nodes[node].ric = true;
seg_nodes[node].c = 1;
}
}
//如果是内部节点
else{
if(seg_nodes[node].count == 0){
seg_nodes[node].lic = seg_nodes[2*node].lic;
seg_nodes[node].ric = seg_nodes[2*node+1].ric;
seg_nodes[node].c = seg_nodes[2*node].c + seg_nodes[2*node+1].c;
if(seg_nodes[2*node].ric == true && seg_nodes[2*node+1].lic == true)
seg_nodes[node].c–;
}
else{
seg_nodes[node].lic = true;
seg_nodes[node].ric = true;
seg_nodes[node].c = 1;
}
}
}
void insert(int node,int begin,int end,int l,int r){
if(l <= begin && end <= r){
seg_nodes[node].count++;
update(node,begin,end);
return ;
}
int mid = begin+(end-begin)/2;
if(l < mid) insert(2*node,begin,mid,l,r);
if(r > mid) insert(2*node+1,mid,end,l,r);
update(node,begin,end);
}
void dele(int node,int begin,int end,int l,int r){
if(l <= begin && end <= r){
seg_nodes[node].count–;
update(node,begin,end);
return;
}
int mid = begin+(end-begin)/2;
if(l < mid) dele(2*node,begin,mid,l,r);
if(r > mid) dele(2*node+1,mid,end,l,r);
update(node,begin,end);
}
struct segment{
int pos;
int lor;
int x;
int y;
segment(){
pos = lor = x = y = 0;
}
segment(int p,int l,int xx,int yy){
pos = p;
lor = l;
x = xx;
y = yy;
}
}segs[2][5001*2];
void quick_sort(segment array[],int begin,int end){
if(begin < end){
int i,j;
for(i = j = begin; i < end ; i++){
if(array[i].pos < array[end].pos){
segment temp = array[i];
array[i] = array[j];
array[j] = temp;
j++;
}
}
segment temp = array[end];
array[end] = array[j];
array[j] = temp;
quick_sort(array,begin,j-1);
quick_sort(array,j+1,end);
}
}
unsigned int sweep_line(segment array[],int size,int begin,int end){
unsigned long area = 0;
build(1,begin,end);
int current,prev;
current = prev = array[0].pos;
for(int i = 0 ; i < size ; ){
current = array[i].pos;
area += (current – prev)*seg_nodes[1].c;
while(i < size && array[i].pos == current){
if(array[i].lor == 0){
insert(1,begin,end,array[i].x,array[i].y);
}else{
dele(1,begin,end,array[i].x,array[i].y);
}
i++;
}
prev = current;
}
return area;
}
void printf_seg(segment array[],int size){
printf("seg:\n");
for(int i = 0 ; i < size ; i++){
printf("%d(%d,%d) ",array[i].pos-10000,array[i].x-10000,array[i].y-10000);
}
printf("\n");
}
void test_insert_dele(int begin,int end){
build(1,begin,end);
printf("%d",num);
insert(1,begin,end,1,3);
insert(1,begin,end,4,5);
insert(1,begin,end,3,4);
dele(1,begin,end,4,5);
printf("seg:%d",seg_nodes[1].c);
}
int main()
{
//test_insert_dele(0,20000);
int n;
int index_x = 0;
int index_y = 0;
unsigned long length = 0;
scanf("%d",&n);
for(int i = 0 ; i < n ; i++){
int llx,lly,urx,ury;
scanf("%d%d%d%d",&llx,&lly,&urx,&ury);
llx += 10000;
lly += 10000;
urx += 10000;
ury += 10000;
//x轴方向的下线段
segs[0][index_x++] = segment(lly,0,llx,urx);
//x轴方向的上线段
segs[0][index_x++] = segment(ury,1,llx,urx);
//y轴方向的左线段
segs[1][index_y++] = segment(llx,0,lly,ury);
//y轴方向的右线段
segs[1][index_y++] = segment(urx,1,lly,ury);
}
//线段排序
quick_sort(segs[0],0,index_x-1);
//printf_seg(segs[0],index_x);
quick_sort(segs[1],0,index_y-1);
//printf_seg(segs[1],index_y);
//建立线段树
//
length += sweep_line(segs[0],index_x,0,20000);
//printf("%d\n",length*2);
length += sweep_line(segs[1],index_y,0,20000);
printf("%d\n",length*2);
return 0;
}