由于数据范围过大,直接线段树会炸,离散化或者动态开点都行。

打个标记在树上,最后把树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 ;
}

最新文章

  1. PXC(Percona XtraDB Cluster)集群的安装与配置
  2. Oracle之分页查询
  3. We Know What @You #Tag: Does the Dual Role Affect Hashtag Adoption-20160520
  4. iOS开发之Objective-C与JavaScript的交互(转载)
  5. ELK+FileBeat+Log4Net搭建日志系统
  6. dhtmlxScheduler日历日程控件包括天视图,周视图,月视图,年视图和日程表视图
  7. Double-checked locking and the Singleton pattern--双重检查加锁失效原因剖析
  8. IE6和IE7下绝对定位position:absolute和margin的冲突问题解决
  9. Python 文件的IO
  10. Drupal 实战
  11. 蓝桥网试题 java 基础练习 矩形面积交
  12. 基于Vue实现后台系统权限控制
  13. JavaScript之数组五大迭代方法总结
  14. vue中如何获取后台数据
  15. PHP多个一维数组合并成二维数组的简易方法
  16. Jenkins 的安装部署
  17. IOS中的三大事件
  18. Beta阶段冲刺2.0
  19. vi命令【方向键】变字母键的解决方法
  20. 2017-2018-2 20155310『网络对抗技术』Exp5:MSF基础应用

热门文章

  1. 剑指offer-旋转数组的最小数字06
  2. UZH slam 两种相机
  3. BZOJ 4592 SHOI2015 脑洞治疗仪 线段树
  4. 数据结构7——DP优化
  5. Daily Scrum02 12.05
  6. JMS实战——ActiveMQ
  7. 推荐一个好的Redis GUI 客户端工具
  8. DataView RowFilter Syntax [C#]
  9. Hibernate映射关系之_多对多
  10. 【bzoj2384】[Ceoi2011]Match 特殊匹配条件的KMP+树状数组