BZOJ 1645 [Usaco2007 Open]City Horizon 城市地平线

题目大意

给你一个平面直角坐标系，每次指定一个(x,y)区间有一个高度为h的建筑。问建筑相互覆盖之后的总面积（每个位置的高度按最高的建筑计算）

这道题我们想到相互覆盖，区间覆盖……线段树无疑。

首先x,y范围是1e9但是只有40000个建筑所以我们首先要进行离散化。

如何离散化？

我们搞一个结构体（我把它起名sorttmp,简称ST嘿嘿嘿），里面存着旧的值，新的值和唯一（也可以不唯一）的编号。

我们首先通过编号建立每一个值和对应的值（在这道题里就是l,r和对应的值的对应关系），确保离散化之后可以搞回来。

之后我们按照旧的值的大小sort一次。

之后我们赋上新值，同时用一个数组记录新的值映射旧的值（反着映射没用QwQ

之后我们按照唯一id排序，把整个序列搞回原来的模样，之后对每个l,r赋上新的值。

从此离散化结束，如果需要调用旧值直接访问refer[]数组就可以找到对应的映射。

之后我们按h从小到大排序进行覆盖，这样就可以保证我们最终每个位置上的都是最高的建筑（我还在想咋特判QwQ）

还有一个需要注意的是我们维护的是线段而不是点，所以在维护的时候特判条件是不一样的。

我的线段树板子写错了又对拍又调试的花了整整一天……以后再也不敢原来的写法和现在的写法混用了我还是用着新写法吧QwQ

#include <bits/stdc++.h>
using namespace std;
struct segtree
{
    long long val,laz;
}s[300010];
struct query
{
    int l,r,h;
}q[60010];
struct sorttmp
{
    int ori,val,id;
    bool flg;
}st[100010];
bool cmpa(sorttmp tx,sorttmp ty) {return tx.ori<ty.ori;}
bool cmpb(sorttmp tx,sorttmp ty) {if(tx.flg==ty.flg)return tx.id<ty.id; return tx.flg<ty.flg;}
bool cmpc(query tx,query ty) {return tx.h<ty.h;}
int n,nm,sttop,refer[100010];
void pushdown(int pos,int l,int r)
{
    if(!s[pos].laz) return;
    int mid=(l+r)>>1;
    s[pos<<1].val=s[pos].laz*(refer[mid]-refer[l]);
    s[(pos<<1)+1].val=s[pos].laz*(refer[r]-refer[mid]);
    s[pos<<1].laz=s[pos].laz;
    s[(pos<<1)+1].laz=s[pos].laz;
    s[pos].laz=0;
    return;
}
void updata(int pos,int l,int r,int x,int y,long long z)
{
    if(x<=l&&r<=y) {s[pos].val=z*(refer[r]-refer[l]);s[pos].laz=z;return;}
    pushdown(pos,l,r);
    int mid=(l+r)>>1;
    if(y>mid) updata((pos<<1)+1,mid,r,x,y,z);
    if(x<mid) updata(pos<<1,l,mid,x,y,z);
    s[pos].val=s[pos<<1].val+s[(pos<<1)+1].val;
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
        st[++sttop].ori=q[i].l,st[sttop].id=i;
        st[++sttop].ori=q[i].r,st[sttop].id=i,st[sttop].flg=true;
    }
    sort(st+1,st+sttop+1,cmpa);
    st[0].ori=-1;
    for(int i=1;i<=sttop;++i)
    {
        if(st[i].ori!=st[i-1].ori) ++nm;
        st[i].val=nm;
        refer[nm]=st[i].ori;
    }
    sort(st+1,st+sttop+1,cmpb);
    for(int i=1;i<=n;++i) q[i].l=st[i].val,q[i].r=st[n+i].val;
    sort(q+1,q+n+1,cmpc);
    for(int i=1;i<=n;++i) updata(1,1,nm,q[i].l,q[i].r,q[i].h);
    printf("%lld",s[1].val);
}