hdu1542用线段树A过~
1542这个题用线段树做,有两个收获,一是复习了类似的离散化,段更新求面积周长的方法,另外,就是学到了如何把“点值”转换成“段值”,线段树本质上,是对段的操作,但坐标值,是一个点值,所以要想用线段树解决,就必须把点值转换成段值,首先离散化,离散成一段一段的,把大的点值-1,当成段值,可以想象,一个含有n个点的线段,其实只有n-1个小段,所以要-1,当然要考虑只有一个点的情况要特殊处理,然后在更新总和的时候,要把段还原成点,这样就可以用“段”求“点”了~
今天下午一直昏昏沉沉,提不起精神,勉强做了这个题,希望是个转折吧
#include "stdio.h"
#include "algorithm"
using namespace std;
struct {
int l,r;
int cnt;
double sum;
int getmid(){
return (l+r)/2;
}
}st[6666];//横线段的线段树
struct SS{
double l,r;
double h;
int s;
}ss[6666];//横线段
double pos[6666];//横坐标
int k;//横坐标的个数
int bin(int c);
bool cmp(struct SS&a,struct SS&b){
return a.h<b.h;
}
void build(int a,int b,int ind){
st[ind].l=a;
st[ind].r=b;
st[ind].cnt=0;
st[ind].sum=0;
if(a==b)
return ;
int mid=st[ind].getmid();
build(a,mid,ind*2);
build(mid+1,b,ind*2+1);
}
void update(int ind){
if(st[ind].cnt){
st[ind].sum=pos[st[ind].r+1]-pos[st[ind].l];//在计算和时,还原点值,所以+1
}else if(st[ind].l==st[ind].r){
st[ind].sum=0;
}
else{
st[ind].sum=st[ind*2].sum+st[ind*2+1].sum;
}
}
void insert(int a,int b,int c,int ind){
if(a<=st[ind].l&&st[ind].r<=b){
st[ind].cnt+=c;
}else{
int mid=st[ind].getmid();
if(a<=mid)
insert(a,b,c,ind*2);
if(b>mid)
insert(a,b,c,ind*2+1);
}
update(ind);
}
int bin(double c){
int p,q;
p=0;
q=k-1;
while(p<=q){
int mid=(p+q)/2;
if(pos[mid]==c)
return mid;
if(pos[mid]<c)
p=mid+1;
else
q=mid-1;
}
return -1;
}
int main(){
int n,m;
double x1,x2;
int cx=-1;
for(;;){
scanf("%d",&n);
if(n==0)