【bzoj4636】蒟蒻的数列
2024-08-28 19:01:29
由于数据范围过大,直接线段树会炸,离散化或者动态开点都行。
打个标记在树上,最后把树dfs一边算一下即可。
#include<bits/stdc++.h>
#define N 10000010
#define inf 1000000000
using namespace std;
typedef long long ll;
int tot=,sumv[N<<],ls[N],rs[N];
int n,rt,cnt=;ll ans=;
void change(int &o,int l,int r,int ql,int qr,int v){
if(l>r)return;
if(!o)o=++cnt;
if(ql<=l&&r<=qr){sumv[o]=max(sumv[o],v);return;}
int mid=(l+r)>>;
if(ql<=mid)change(ls[o],l,mid,ql,qr,v);
if(qr>mid)change(rs[o],mid+,r,ql,qr,v);
}
void dfs(int o,int l,int r,int maxv){
if(!o)return;
maxv=max(maxv,sumv[o]);
if(!ls[o]&&!rs[o]){ans+=1LL*(r-l+)*maxv;return;}
int mid=(l+r)>>;
dfs(ls[o],l,mid,maxv);dfs(rs[o],mid+,r,maxv);
if(!ls[o])ans+=1LL*(mid-l+)*maxv;
if(!rs[o])ans+=1LL*(r-mid)*maxv;
}
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();
for(int i=;i<=n;i++){
int l=read(),r=read(),k=read();
change(rt,,inf,l,r-,k);
}
dfs(rt,,inf,);
printf("%lld\n",ans);
return ;
}
最新文章
- PXC(Percona XtraDB Cluster)集群的安装与配置
- Oracle之分页查询
- We Know What @You #Tag: Does the Dual Role Affect Hashtag Adoption-20160520
- iOS开发之Objective-C与JavaScript的交互(转载)
- ELK+FileBeat+Log4Net搭建日志系统
- dhtmlxScheduler日历日程控件包括天视图,周视图,月视图,年视图和日程表视图
- Double-checked locking and the Singleton pattern--双重检查加锁失效原因剖析
- IE6和IE7下绝对定位position:absolute和margin的冲突问题解决
- Python 文件的IO
- Drupal 实战
- 蓝桥网试题 java 基础练习 矩形面积交
- 基于Vue实现后台系统权限控制
- JavaScript之数组五大迭代方法总结
- vue中如何获取后台数据
- PHP多个一维数组合并成二维数组的简易方法
- Jenkins 的安装部署
- IOS中的三大事件
- Beta阶段冲刺2.0
- vi命令【方向键】变字母键的解决方法
- 2017-2018-2 20155310『网络对抗技术』Exp5:MSF基础应用