【bzoj4636】蒟蒻的数列 离散化+线段树

原文地址: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 <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;
}
上一篇:iOS开发技巧 - 使用UIDatePicker来选择日期和时间


下一篇:hdu6183 Color it 线段树动态开点+查询减枝