BZOJ 4636 蒟蒻的数列

题目大意

给你一个初始全0的序列，每次给出一个a,b,k表示将序号为[a,b)的所有元素小于k的变为k，询问最终的最大值。

继续线段树！

这道题就是离散化+线段树v2.0嘛……欢快的码完，不过样例。

这道题和城市地平线不完全一样。那道题维护的是线段，也就是每个叶子节点离散化后表示的是[a,b]这个线段的权值。

但是这道题我们需要维护的是点。

所以我们很自然地想到，我们可以令叶子结点表示的是离散化之后的[询问点,下一个询问点)的点权和，考虑特殊情况，因为不存在[a,a)所以可行。之后我们需要考虑的就是如何维护。每次枚举的mid我们归到左儿子去，这样的话就有左儿子代表的是[l,mid]，此时点的个数为refer[mid+1]-refer[l]，右儿子是refer[r+1]-refer[mid+1]。对于每次更新传入的update参数中(x,y)为(q[i].l,q[i].r-1)，原因大家可以自行画图思考。

#include <bits/stdc++.h>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
const int maxN=100010;
struct query
{
    int l,r,h;
}q[maxN];
struct sorttmp
{
    int ori,val,id;
    bool flg;
}st[maxN<<1];
int n,sttop;
long long sum[maxN<<2],laz[maxN<<2],refer[maxN<<3];
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;}
void pushup(int pos) {sum[pos]=sum[lson]+sum[rson];}
void pushdown(int pos,int l,int r)
{
    if(laz[pos])
    {
        int mid=(l+r)>>1;
        laz[lson]=laz[rson]=laz[pos];
        laz[pos]=0;
        sum[lson]=laz[lson]*(refer[mid+1]-refer[l]);
        sum[rson]=laz[rson]*(refer[r+1]-refer[mid+1]);
        return;
    }
}
void update(int pos,int l,int r,int x,int y,long long z)
{
    if(x<=l&&r<=y) {sum[pos]=(refer[r+1]-refer[l])*z,laz[pos]=z;return;}
    int mid=(l+r)>>1;
    pushdown(pos,l,r);
    if(x<=mid) update(lson,l,mid,x,y,z);
    if(y>mid) update(rson,mid+1,r,x,y,z);
    pushup(pos);
    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);
    for(int i=1;i<=n;++i) 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);
    int tmp=0;
    st[0].ori=-0x7fffffff;
    for(int i=1;i<=sttop;++i)
    {
        if(st[i-1].ori!=st[i].ori) ++tmp;
        st[i].val=tmp;
        refer[tmp]=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)
        if(q[i].l!=q[i].r) update(1,1,tmp,q[i].l,q[i].r-1,q[i].h);
    printf("%lld",sum[1]);
}