学步园

思路：线段树+离散化 因为它们的宽度太大，无法存储 所以得离散
PS：这道题又学到了一些新知道 1、另一种离散化的方法 2、unique 函数的使用

 unique(first,last)
参数 first, last:指出要剔除连续重复元素的迭代器区间[first,last) 
右边是开区间
返回值  返回剔除元素后的新区间的最后一个元素的迭代器位置

//   
4028K   
204MS
#include <stdio.h>
#include <algorithm>
#define M 40050
#define L(x) (x<<1)
#define R(x) ((x<<1)+1)
using namespace std;

struct data
{
    int
l,r,h;
}node[8*M];

int seg[2*M],hei[M],lp[M],rp[M];

void BuildTree(int left,int right,int u)
{
    node[u].l =
left;
    node[u].r =
right;
    node[u].h =
0;
    if (left + 1
== right)
       
return ;
    int mid =
(left + right)>>1;
    BuildTree
(left,mid,L(u));
    BuildTree
(mid,right,R(u));
}

void updata (int left,int right,int i,int u)
{
    if
(seg[node[u].l] ==
left&&seg[node[u].r] ==
right)//找到与原来长度相等的
    {
       
if (node[u].h <
hei[i])      
//比已存在的高 就把它覆盖
           
node[u].h = hei[i];
       
return ;
    }
    int mid =
seg[(node[u].l+node[u].r)>>1];
    if (right
<= mid)
       
updata (left,right,i,L(u));
    else if
(left >= mid)
       
updata (left,right,i,R(u));
    else
    {
       
updata (left,mid,i,L(u));
       
updata (mid,right,i,R(u));
    }
}

__int64 count (int h,int
u)   
//算每个子结点的面积并
{
    if
(node[u].h <
h)         
//延迟覆盖 父结比子结点高的话
       
node[u].h = h;
    if
(node[u].l + 1 == node[u].r)
       
return (__int64) (seg[node[u].r] - seg[node[u].l]
)*node[u].h;
    __int64 a =
count (node[u].h,L(u));
    __int64 b =
count (node[u].h,R(u));
    return
a+b;
}
int main ()
{
    int
n,m,a,b,i;

    while
(~scanf ("%d",&n))
    {
       
int k = 0;
       
for (i = 1;i <= n;i
++)         
//离散化操作
       
{
           
scanf
("%d%d%d",&lp[i],&rp[i],&hei[i]);

           
seg[++k] = lp[i];
           
seg[++k] = rp[i];
       
}