线段树典型例题--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);}