题目描述

Description

蒟蒻DCrusher不仅喜欢玩扑克，还喜欢研究数列
题目描述
DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b)这个区间中所有比k小的数改为k，他想知
道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。

Input

第一行一个整数N，然后有N行，每行三个正整数a、b、k。
N<=40000 , a、b、k<=10^9

Output

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

Sample Input

4
2 5 1
9 10 4
6 8 2
4 6 3

Sample Output

16

题目分析

将操作离线 按c排序之后就成了线段树区间覆盖问题
因为坐标太大 使用动态开点线段树

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int root;
struct your
{
    int x,y,sum;
    int lson,rson;
}a[50010<<8];
int n;
int size;
void update(int dx,int dy,int l,int r,int c,int &root)
{
    if(dx>dy) return ;
    if(!root) root=++size,a[root].x=l,a[root].y=r;
    if(a[root].x==dx&&a[root].y==dy)
    {
        a[root].sum=max(c,a[root].sum);
        return ;
    }   
    int mid=(a[root].x+a[root].y)>>1;
    if(dy<=mid) update(dx,dy,l,mid,c,a[root].lson);
    else if(dx>mid) update(dx,dy,mid+1,r,c,a[root].rson);
    else update(dx,mid,l,mid,c,a[root].lson),update(mid+1,dy,mid+1,r,c,a[root].rson);  
}
long long ans=0;
void dfs(int dx,int dy,int c,int root)
{
    if(!root) return ;
    a[root].sum=max(a[root].sum,c);
    if(!a[root].lson&&!a[root].rson) 
    {
        ans+=(long long) a[root].sum*(a[root].y-a[root].x+1);
        return ;
    }
    int mid=(dx+dy)>>1;
    dfs(dx,mid,a[root].sum,a[root].lson),dfs(mid+1,dy,a[root].sum,a[root].rson);
    if(!a[root].lson) ans+=(long long) a[root].sum*(mid-dx+1);
    if(!a[root].rson) ans+=(long long) a[root].sum*(dy-mid);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        update(x,y-1,1,1000000000,c,root);
    }
    dfs(1,1000000000,0,root);
    printf("%lld",ans);
    return 0;
}