POJ 3277 City Horizon(叶子节点为[a,a+1)的线段树+离散化)

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
/*
题意：
给出一条直线上的矩形左右坐标和高度，求所有矩形并的面积。
思路：
这里处理没有跟以前的线段树一样，这里每个叶子节点代表的是区间[a,a+1）,而不像以前的代表一个点(a,a);
需要建立基本单位为线段的线段树，建法与以点为单位的线段树就一点点不同，具体见代码。这样可以方便在离散化后求一段区间间的长度由于A、B的值太大，需要离散。且不可能开那么大的数组，也就不能通过A、B直接获取他们的映射值。
而只能通过他们映射的值来获取对应的A、B，用二分查找。
由于最后求并的面积，为方便起见，可以先将矩形按高度从小到大排序，后面的覆盖前面的即可。在discuss里别人写的几个注意点：
总算有点收获，总结以下几点
1、离散的时候要用二分来查找映射值
2、数据全部用long long 吧，比较保险
3、数组开大点，因为一共有40000组数据，每组数据两个点，加起来也就是有大约80000个点，所以N要开到80000，存线段树的数组要开到4*N。
4、题目的意思是要算矩形和，也就是说同一个线段上有多个高度的话，取最高的那个，再modify的时候，
可以先对输入的数据根据高度从小到大排序，在接下来的操作中直接覆盖，这样就可以避免一些不必要的麻烦。*/
using namespace std;
const int maxn=;
int n;
int cnt;
long long vk[maxn*]; //vk[i]=A，表示A映射的值为i，要通过二分查找，寻找A对应的映射值
long long val[maxn*];
struct Tree{
long long sum; //该区间的矩阵面积
long long num; //该区间的矩阵高度
bool lazy;
}tree[maxn<<];
struct Node{
long long a,b,h; //区间[a,b]，以及高度h
bool operator<(const Node tmp)const{
return h<tmp.h;
}
}node[maxn];//二分查找k对应的映射值
int binsearch(long long k){
int l=,r=cnt,mid;
while(l<=r){
mid=(l+r)>>;
if(vk[mid]==k)
return mid;
if(vk[mid]<k)
l=mid+;
else
r=mid-;
}
return -; //肯定会查找的到，这里就是摆设
}void build(int rt,int L,int R){
tree[rt].sum=;
tree[rt].num=;
tree[rt].lazy=false;
if(L+==R) //这才是重点啊，建立区间为[a,a+1)的叶子节点
return;
int mid=(L+R)>>;
build(rt<<,L,mid);
build(rt<<|,mid,R); //右儿子：mid~R
}void pushUp(int rt){
tree[rt].sum=(tree[rt<<].sum+tree[rt<<|].sum);
}void pushDown(int rt,int L,int R){
if(tree[rt].lazy){
int lson=rt<<,rson=rt<<|;
int mid=(L+R)>>;
long long l1=vk[L],r1=vk[mid],l2=vk[mid],r2=vk[R],length1,length2;
tree[lson].num=tree[rson].num=tree[rt].num;
length1=r1-l1;length2=r2-l2; //左儿子对应的区间长度和右儿子对应的区间长度
tree[lson].sum=length1*tree[rt].num;
tree[rson].sum=length2*tree[rt].num;
tree[lson].lazy=tree[rson].lazy=true;
tree[rt].lazy=false;
}
}
//L,R是节点rt的区间，l,r是要更新的区间目标
void update(int rt,int L,int R,int l,int r,long long h){
long long left=vk[L],right=vk[R],length;
if(l<=L && R<=r){
tree[rt].num=h;
length=right-left;
tree[rt].sum=h*length;
tree[rt].lazy=true;
return;
}
pushDown(rt,L,R);
int mid=(L+R)>>;
//注意两个if条件里面不能有等号
if(l<mid)
update(rt<<,L,mid,l,r,h);
if(r>mid)
update(rt<<|,mid,R,l,r,h);
//也可以下面注释的语句
/*
if(r<=mid)
update(rt<<1,L,mid,l,r,h);
else if(l>=mid)
update(rt<<1|1,mid,R,l,r,h);
else{
update(rt<<1,L,mid,l,mid,h);
update(rt<<1|1,mid,R,mid,r,h);
}
*/
pushUp(rt);
}
int main()
{
long long a,b,h;
int idx=;
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%I64d%I64d%I64d",&a,&b,&h);
node[i].a=a;
node[i].b=b;
node[i].h=h;
val[idx++]=a;
val[idx++]=b;
}
//离散化
sort(val,val+idx);
cnt=;
vk[cnt]=val[];
for(int i=;i<idx;i++){
if(val[i]==val[i-])
continue;
vk[++cnt]=val[i]; //只不过这里建立的是映射————key
} build(,,cnt);
sort(node,node+n);
int x,y;
for(int i=;i<n;i++){
//二分查找，获取映射
x=binsearch(node[i].a);
y=binsearch(node[i].b);
//printf("%I64d %I64d: %d %d\n",node[i].a,node[i].b,x,y);
update(,,cnt,x,y,node[i].h);
}
printf("%I64d\n",tree[].sum);
return ;
}