原文地址：http://www.cnblogs.com/GXZlegend/p/6801379.html
题目描述
蒟蒻DCrusher不仅喜欢玩扑克，还喜欢研究数列
题目描述
DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b)这个区间中所有比k小的数改为k，他想知道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。
输入
第一行一个整数N，然后有N行，每行三个正整数a、b、k。
N<=40000 , a、b、k<=10^9
输出
一个数，数列中所有元素的和
样例输入
4 2 5 1 9 10 4 6 8 2 4 6 3
样例输出
16
题解
离散化+线段树
很容易想到先将操作按照k值从小到大排序，然后按照这个顺序修改，就不用考虑大于等于k的数。
题目中给的是[a,b)的点，可以转化成a到b的线段，便于离散化。
离散化后线段树区间修改即可，注意这是维护线段的线段树，和维护点权的线段树略有区别。
#include#include #include #define N 40010#define lson l , mid , x << 1#define rson mid , r , x << 1 | 1using 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;}