4636: 蒟蒻的数列
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 145 Solved: 71
[Submit][Status][Discuss]
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
2 5 1
9 10 4
6 8 2
4 6 3
Sample Output
16
在线段树上打标记（动态开节点）
节点数不会超过40000*log（1e9)
然后dfs统计即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<cstring>
#define yyj(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);
#define llg long long
#define maxn 1200000*2
#define inf 1000000000
struct node
{
llg lc,rc;
}a[maxn];
llg i,j,k,x,n,m,y,L,R,val[maxn],ans,cnt;
using namespace std;
void make(llg o,llg l,llg r)
{
if (l>=L && r<=R)
{
val[o]=max(val[o],k);
return;
}
llg mid=(l+r)/;
if (L<=mid)
{
if (a[o].lc==)
{
cnt++; a[o].lc=cnt;
}
make(a[o].lc,l,mid);
}
if (R>mid)
{
if (a[o].rc==)
{
cnt++; a[o].rc=cnt;
}
make(a[o].rc,mid+,r);
}
}
void dfs(llg o,llg l,llg r,llg w)
{
llg now=max(val[o],w),mid=(l+r)/;
if (a[o].lc!=) dfs(a[o].lc,l,mid,now);
else ans+=(mid-l+)*now;
if (a[o].rc!=) dfs(a[o].rc,mid+,r,now);
else ans+=(r-mid)*now;
}
int main()
{
yyj("a");
cin>>n; cnt=;
for (i=;i<=n;i++)
{
scanf("%lld%lld%lld",&L,&R,&k); R--;
if (L>R) continue;
make(,,inf);
}
dfs(,,inf,);
cout<<ans;
return ;
}