第一道线段树.. 略难。 引用忘了哪看的一句话“10亿的的数据规模是任何数据结构都无能为力的，所以必须离散化”。因为略复杂我用class写的…yzhw牛说“线段树编程复杂度太高，一般用树狀数组或者STL set。不要class，class运行爆慢” 但是哥就是用class和链表过了，怎样！！ 1200ms.. 不过后来看了一下Google到用Pascal的蒟蒻牛的代码，发现树狀数组果然好用！

hw给了我篇论文，我发现现在的程度知道了一个数据结构的意思&&一些优化比如“lazy”，写出来的东西details上面大家都差不多的。比如这道题目的lazy我也是加了个-1作标签说明下面的节点需要递归确认，即这一块不是一大块一样的

优化有二：
1. compress()  每次插入完一个building以后沿着树往下看有没有标记为-1但是左右子树height（toLoad）相等的，如果有合并左右子树。实践证明这个优化对这题的数据用处不大，反而拖到了1800ms…
2. 这个厉害了，没它我算5000的数据都要跑半分钟，而还有两组40000的数据，加了这优化4w的秒出。也是刚刚那篇里提到的“观察发现，线段树的建树、统计操作已难以再优化，但插入操作却任可以优化。由于一开始房子的高度无序，所以每次插入如果全部包含不能直接赋值，还需要向下递归左右子树。其实我们可以先将房子的高度排序，然后再依次插入，这样一旦全部包含就可以直接赋值，程序的效率大大提高。这样这道题就可以AC了。”

代码：

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

struct Building {
  int s,e,h;
};

int searchMap(int map[],int mapN,int value) {
  int p0=0,p1=mapN-1;
  while(p0<p1) {
    int mid=(p0+p1)/2;
    if(value==map[mid])
      p0=p1=mid;
    if(value<map[mid])
      p1=mid-1;
    if(value>map[mid])
      p0=mid+1;
  }
  return p0;
}

class segmentTreeNode {
public:
  int p0,p1;
  int toLoad;
  int mid() {
    return (p0+p1)/2;
  }
  segmentTreeNode *lChild,*rChild,*parent;
  segmentTreeNode(int p0__,int p1__) {
    toLoad=0;
    p0=p0__;
    p1=p1__;
    if(p0==p1-1)
      lChild=rChild=NULL;
    else {
      lChild=new segmentTreeNode(p0,mid());
      lChild->parent=this;
      rChild=new segmentTreeNode(mid(),p1);
      rChild->parent=this;
    }
  }
  ~segmentTreeNode() {
	  delete lChild;
	  delete rChild;
  }
  void load(const int,const int,const int);
  void compress();
  long long result(int map[]);
};

void segmentTreeNode::load(const int p0__,const int p1__,const int height) {
  if(toLoad>=height)
    return;
  if(p0__==p0 && p1__==p1) {
	toLoad=height;
	return;
  }
  if(toLoad>=0) {
	  lChild->toLoad=toLoad;
	  rChild->toLoad=toLoad;
  }
  toLoad=-1;
  if(p0__<mid()) {
    int end=min(p1__,mid());
    lChild->load(p0__,end,height);
  }
  if(p1__>mid()) {
    int start=max(p0__,mid());
    rChild->load(start,p1__,height);
  }
  return;
}

void segmentTreeNode::compress() {
	if(toLoad==-1) {
		lChild->compress();
		rChild->compress();
		if(lChild->toLoad!=-1 && lChild->toLoad==rChild->toLoad)
			toLoad=lChild->toLoad;
	}
}

long long segmentTreeNode::result(int map[]) {
  if(toLoad>=0)
    return ((long long)map[p1]-map[p0])*toLoad;
  return lChild->result(map)+rChild->result(map);
}

int comp(const void *a,const void *b) {
	return *(int *)a-*(int *)b;
}

int comp2(const void *__a,const void *__b) {
	Building *a=(Building *)__a;
	Building *b=(Building *)__b;
	return a->h-b->h;
}

int main() {
  Building building[40000];
  int buildingN;
  scanf("%d",&buildingN);
  int map[80000];
  for(int i=0;i<buildingN;i++) {
    scanf("%d%d%d",&building[i].s,&building[i].e,&building[i].h);
    map[2*i]=building[i].s;
    map[2*i+1]=building[i].e;
  }

  qsort(map,2*buildingN,sizeof(int),comp);

  int p0=0,p1=0;
  while(p1<2*buildingN) {
    if(map[p1]==map[p0]) {
      p1++;
      continue;
    }
    map[++p0]=map[p1];
    p1++;
  }
  int mapN=p0+1;

  segmentTreeNode tree(0,mapN-1);
  tree.parent=NULL;

  qsort(building,buildingN,sizeof(Building),comp2);

  for(int i=0;i<buildingN;i++) {
    int start=searchMap(map,mapN,building[i].s);
    int end=searchMap(map,mapN,building[i].e);
    int height=building[i].h;
    tree.load(start,end,height);
    //tree.compress();
  }

  printf("%lld\n",tree.result(map));

  return 0;
}