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

题目描述

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

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

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

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 40010

#define lson l , mid , x << 1

#define rson mid , r , x << 1 | 1

using namespace std;

typedef long long ll;

struct pos

{

	int num , p;

}a[N << 1];

struct seg

{

	int lp , rp , k;

}q[N];

int v[N << 1] , top , tag[N << 3];

ll sum[N << 3];

bool cmp1(pos a , pos b)

{

	return a.num < b.num;

}

bool cmp2(seg a , seg b)

{

	return a.k < b.k;

}

void pushup(int x)

{

	sum[x] = sum[x << 1] + sum[x << 1 | 1];

}

void pushdown(int l , int r , int x)

{

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

	if(tag[x])

	{

		sum[x << 1] = (ll)(v[mid] - v[l]) * tag[x];

		sum[x << 1 | 1] = (ll)(v[r] - v[mid]) * tag[x];

		tag[x << 1] = tag[x << 1 | 1] = tag[x];

		tag[x] = 0;

	}

}

void update(int b , int e , int k , int l , int r , int x)

{

	if(b <= l && r <= e)

	{

		sum[x] = (ll)(v[r] - v[l]) * k;

		tag[x] = k;

		return;

	}

	pushdown(l , r , x);

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

	if(b < mid) update(b , e , k , lson);

	if(e > mid) update(b , e , k , rson);

	pushup(x);

}

int main()

{

	int n , i;

	scanf("%d" , &n);

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

		scanf("%d%d%d" , &a[i].num , &a[i + n].num , &q[i].k) , a[i].p = i , a[i + n].p = i + n;

	sort(a + 1 , a + 2 * n + 1 , cmp1);

	for(i = 1 ; i <= 2 * n ; i ++ )

	{

		if(a[i].num != v[top]) v[++top] = a[i].num;

		if(a[i].p <= n) q[a[i].p].lp = top;

		else q[a[i].p - n].rp = top;

	}

	sort(q + 1 , q + n + 1 , cmp2);

	for(i = 1 ; i <= n ; i ++ ) update(q[i].lp , q[i].rp , q[i].k , 1 , top , 1);

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

	return 0;

}