线段树典型例题--poj3277
将x轴上的点离散化。
y轴建立线段树。使用延迟标记。
注意：延迟标记不是单纯覆盖，而是需要比较的。
pp[i]为标记
则应当是
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <algorithm>using namespace std;const int N=70005;int g[N*4],mm[N*10],pp[N*10],x[N],y[N],h[N];int tot,n,i;long long ans,tmp;void down(int i){ if (pp[i]==0) return; mm[i*2]=max(mm[i*2],pp[i]); mm[i*2+1]=max(mm[i*2+1],pp[i]); pp[i*2]=max(pp[i*2],pp[i]); pp[i*2+1]=max(pp[i*2+1],pp[i]); pp[i]=0;}void ins(int i,int l,int r,int x,int y,int h){ if (x<=l && y>=r) { mm[i]=max(mm[i],h); pp[i]=max(pp[i],h); return; } down(i); int mid=(l+r)/2; if (x<mid) ins(i*2,l,mid,x,y,h); if (y>mid) ins(i*2+1,mid,r,x,y,h);}int find(int i,int l,int r,int x){ if (l+1==r) return mm[i]; down(i); int mid=(l+r)/2; if (x<mid) return find(i*2,l,mid,x); else return find(i*2+1,mid,r,x);}int main(){ freopen("in","r",stdin); scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d%d%d",&x[i],&y[i],&h[i]); g[tot++]=x[i]; g[tot++]=y[i]; } sort(g,g+tot); tot=unique(g,g+tot)-g; for (i=1;i<=n;i++) { x[i]=lower_bound(g,g+tot,x[i])-g+1; y[i]=lower_bound(g,g+tot,y[i])-g+1; ins(1,1,tot,x[i],y[i],h[i]); } for (i=0;i<tot-1;i++) { tmp=find(1,1,tot,i+1); tmp*=g[i+1]-g[i]; ans+=tmp; } printf("%lld",ans);}