蒟蒻DCrusher不仅喜欢玩扑克，还喜欢研究数列

题目描述

DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b)这个区间中所有比k小的数改为k，他想知

道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。

第一行一个整数N，然后有N行，每行三个正整数a、b、k。

N<=40000 , a、b、k<=10^9

一个数，数列中所有元素的和

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stdlib.h>

using namespace std;

#define N 40050

#define maxn 1000000000

typedef long long ll;

struct A {

    int l,r,k;

}a[N];

bool cmp(const A &x,const A &y) {return x.k<y.k;}

int tag[N*80],cnt,n,ls[N*80],rs[N*80];

ll t[N*80];

/*int make(int x) {

    return lower_bound(v+1,v+cnt+1,x)-v;

}*/

void pushdown(int l,int r,int &p,int w) {

    if(!p) p=++cnt;

    t[p]=1ll*w*(r-l+1); tag[p]=w;

}

void update(int l,int r,int x,int y,int w,int &p) {

    if(p==0) p=++cnt;

    if(x<=l&&y>=r) {

        t[p]=1ll*w*(r-l+1);

        tag[p]=w;

        return ;

    }

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

    if(tag[p]) {

        pushdown(l,mid,ls[p],tag[p]);

        pushdown(mid+1,r,rs[p],tag[p]);

        tag[p]=0;

    }

    if(x<=mid) update(l,mid,x,y,w,ls[p]);

    if(y>mid) update(mid+1,r,x,y,w,rs[p]);

    t[p]=t[ls[p]]+t[rs[p]];

}

int main() {

    scanf("%d",&n);

    int i;

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

        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);

        a[i].r--;

        /*v[++cnt]=a[i].l;

        v[++cnt]=a[i].r;*/

    }

    /*sort(v+1,v+cnt+1);

    cnt=unique(v+1,v+cnt+1)-v-1;

    printf("%d\n",cnt);

    for(i=1;i<=cnt;i++) printf("%d\n",v[i]); */

    sort(a+1,a+n+1,cmp);

    int root=0;

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

        if(a[i].k==0) continue;

        /*printf("%d %d\n",make(a[i].l),make(a[i].r));

        update(1,cnt,make(a[i].l),make(a[i].r),a[i].k,1);

        printf("sum=%lld\n",t[1]);*/

        update(1,maxn,a[i].l,a[i].r,a[i].k,root);

    }

    printf("%lld\n",t[1]);

}