Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom12月前

07/14
09:08
线段树

[bzoj 4636] 蒟蒻的数列

♦♦♦♦♦♦   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

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

直接线段树动态开点就好了qaq

 

[bzoj 4636] 蒟蒻的数列