链接：F. Finally, christmas!
题意 求图中所视矩形的面积。
思路： 线段树维护每一段区间高度的最大值，然后枚举每一个小的区间，即可得到答案，需要离散化矩形的横坐标，并且在计算面积是要用离散化之前的宽度。
代码：
#include<iostream> #include<cstdio> #include<map> #include<math.h> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=4e5+7; typedef long long ll; ll ma[maxn<<1],la[maxn<<1]; ll temp[maxn]; struct node{ ll l,r,h; }q[maxn<<1]; void pushdown(int rt){ if(la[rt]!=0){ ma[rt<<1]=max(ma[rt<<1],la[rt]); ma[rt<<1|1]=max(ma[rt<<1|1],la[rt]); la[rt<<1]=max(la[rt<<1],la[rt]); la[rt<<1|1]=max(la[rt<<1|1],la[rt]); la[rt]=0; } } void update(int L,int R,int l,int r,ll val,int rt){ if(L<=l&&R>=r){ ma[rt]=max(ma[rt],val); la[rt]=max(la[rt],val); return ; } pushdown(rt); int mid=(l+r)/2; if(L<=mid) update(L,R,l,mid,val,rt<<1); if(R>mid) update(L,R,mid+1,r,val,rt<<1|1); ma[rt]=max(ma[rt<<1],ma[rt<<1|1]); } ll query(int L,int R,int l,int r,int rt){ ll ans=0; if(L<=l&&R>=r){ return ma[rt]; } pushdown(rt); int mid=(l+r)/2; if(L<=mid) ans=max(ans,query(L,R,l,mid,rt<<1)); if(R>mid) ans=max(ans,query(L,R,mid+1,r,rt<<1|1)); return ans; } int main (){ int n,k=0; ll ans=0; cin>>n; for(int i=0;i<n;i++){ scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].h); temp[k++]=q[i].l; temp[k++]=q[i].r; } sort(temp,temp+k); int cnt=unique(temp,temp+k)-temp; for(int i=0;i<n;i++){ int L=lower_bound(temp,temp+cnt,q[i].l)-temp+1; int R=lower_bound(temp,temp+cnt,q[i].r)-temp+1; update(L,R-1,1,cnt,q[i].h,1); //这里只要更新到 R-1,每个节点的权值实际代表 以该点为左端点的区间的权值。 } for(int i=1;i<cnt;i++){ ans+=query(i,i,1,cnt,1)*(temp[i]-temp[i-1]); } printf ("%lld\n",ans); }