poj1208，【POJ3277】City Horizon，线段树

Time:2016.07.15
Author:xiaoyimi
转载注明出处谢谢

传送门
思路：
愚蠢的线段树
离散化x轴后记录各个区间的$y_{max}$
不要想着先去统计面积
最后把标记传一传，统计各个叶子节点的和
这么纸张的题都没有看出来
毕竟状态恢复中…
期末考滚粗后就感觉一直在颓废，药丸(ノ｀Д)ノ‘
注意：
叶子节点存的是相邻的两个离散区间，比如叶子节点[2,3]中$y_{max}=5$，离散值2,3的原值为5,7，则这个节点对答案的贡献就是(7-5)*5=10
代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define M 40005
#define LL long long
#define int long long
using namespace std;
int n,m;    LL ans=0;
int tr[M<<3],num[M<<1],hash[M<<1];
struct node{int l,r,h;
}a[M];
int in()
{int t=0;char ch=getchar();while (ch>'9'||ch<'0') ch=getchar();while (ch>='0'&&ch<='9') t=(t<<3)+(t<<1)+ch-48,ch=getchar();return t;
}
void update(int rt,int begin,int end,node k)
{if (k.l<=begin&&end<=k.r){tr[rt]=max(k.h,tr[rt]);return;}int mid=begin+end>>1;if (mid>k.l) update(rt<<1,begin,mid,k);if (mid<k.r) update(rt<<1|1,mid,end,k);
}
void pushdown(int rt,int begin,int end)
{if (rt>1&&tr[rt>>1]>tr[rt]) tr[rt]=tr[rt>>1];if (begin==end-1) {ans+=(LL)(hash[end]-hash[begin])*tr[rt];return;}int mid=begin+end>>1;pushdown(rt<<1,begin,mid);pushdown(rt<<1|1,mid,end);
}
main()
{n=in();for (int i=1;i<=n;i++)a[i].l=in(),a[i].r=in(),a[i].h=in(),num[(i<<1)-1]=a[i].l,num[i<<1]=a[i].r;sort(num+1,num+n+n+1);for (int i=1;i<=n;i++){int t1=lower_bound(num+1,num+n+n+1,a[i].l)-num,t2=lower_bound(num+1,num+n+n+1,a[i].r)-num;hash[t1]=a[i].l;a[i].l=t1;hash[t2]=a[i].r;a[i].r=t2;update(1,1,n<<1,a[i]);}pushdown(1,1,n<<1);printf("%I64d\n",ans);
}