网上还有用unique函数和lowerbound函数离散的方法，可以百度搜下题解就有。
这里给出介绍unique函数的链接：http://www.cnblogs.com/zhangshu/archive/2011/07/23/2115090.html
#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=40010; int n; int cnt; long long vk[maxn*2]; //vk[i]=A，表示A映射的值为i，要通过二分查找，寻找A对应的映射值 long long val[maxn*2]; struct Tree{ long long sum; //该区间的矩阵面积 long long num; //该区间的矩阵高度 bool lazy; }tree[maxn<<3]; 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=0,r=cnt,mid; while(l<=r){ mid=(l+r)>>1; if(vk[mid]==k) return mid; if(vk[mid]<k) l=mid+1; else r=mid-1; } return -1; //肯定会查找的到，这里就是摆设 } void build(int rt,int L,int R){ tree[rt].sum=0; tree[rt].num=0; tree[rt].lazy=false; if(L+1==R) //这才是重点啊，建立区间为[a,a+1)的叶子节点 return; int mid=(L+R)>>1; build(rt<<1,L,mid); build(rt<<1|1,mid,R); //右儿子：mid~R } void pushUp(int rt){ tree[rt].sum=(tree[rt<<1].sum+tree[rt<<1|1].sum); } void pushDown(int rt,int L,int R){ if(tree[rt].lazy){ int lson=rt<<1,rson=rt<<1|1; int mid=(L+R)>>1; 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)>>1; //注意两个if条件里面不能有等号 if(l<mid) update(rt<<1,L,mid,l,r,h); if(r>mid) update(rt<<1|1,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=0; scanf("%d",&n); for(int i=0;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=1; vk[cnt]=val[0]; for(int i=1;i<idx;i++){ if(val[i]==val[i-1]) continue; vk[++cnt]=val[i]; //只不过这里建立的是映射————key } build(1,1,cnt); sort(node,node+n); int x,y; for(int i=0;i<n;i++){ //二分查找，获取映射 x=binsearch(node[i].a); y=binsearch(node[i].b); //printf("%I64d %I64d: %d %d ",node[i].a,node[i].b,x,y); update(1,1,cnt,x,y,node[i].h); } printf("%I64d ",tree[1].sum); return 0; }