BZOJ 4636 （动态开节点）线段树

思路：

偷懒 懒得离散化

搞了个动态开节点的线段树 （其实是一样的……..）

注意会有a=b的情况 要判掉

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,xx,yy,zz,root,cnt,inf=1000000000,tree[22222222],lson[22222222],rson[22222222];

long long ans;

void insert(int l,int r,int &pos,int L,int R,int Wei){

    if(!pos)pos=++cnt;

    if(l>=L&&r<=R){tree[pos]=max(tree[pos],Wei);return;}

    int mid=(l+r)>>1;

    if(mid<L)insert(mid+1,r,rson[pos],L,R,Wei);

    else if(mid>=R)insert(l,mid,lson[pos],L,R,Wei);

    else insert(l,mid,lson[pos],L,R,Wei),insert(mid+1,r,rson[pos],L,R,Wei);

}

void dfs(int l,int r,int x,int Wei){

    if(!x){ans+=(r-l+1)*Wei;return;}

    int mid=(l+r)>>1;

    dfs(l,mid,lson[x],max(Wei,tree[lson[x]]));

    dfs(mid+1,r,rson[x],max(Wei,tree[rson[x]]));

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d%d%d",&xx,&yy,&zz);

        if(xx==yy)continue;

        insert(1,inf,root,xx,yy-1,zz);

    }

    dfs(1,inf,root,0);

    printf("%lld\n",ans);

}