现在的位置: 首页 > 综合 > 正文

【线段树】HDU1542 线段树求面积周长

2018年04月12日 ⁄ 综合 ⁄ 共 1612字 ⁄ 字号 评论关闭

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)
       

抱歉!评论已关闭.