题目大意:输入n,m,k。n个数,m个区间更新标记为1~m。n次操作,每次操作有两个数x,y表示执行第x~y个区间更新。

题解:通过差分来表示某个区间更新操作执行的次数。然后用线段树来更新区间。

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+;
typedef long long ll;
ll arr[N];
ll tt[N],cnt[N];
struct stu{
ll value,add;
}tree[N+N+N];
ll l1[N],r1[N],v[N];
void bt(ll root,ll start,ll end){
tree[root].add=;
if(start==end) {
tree[root].value=arr[end];
return ;
}
ll mid=(start+end)/;
bt(root*,start,mid);
bt(root*+,mid+,end);
tree[root].value=tree[root*].value+tree[root*+].value;
}
void pushdown(ll root,ll start,ll end){
ll mid=(start+end)/;
tree[root*].value+=(mid-start+)*tree[root].add;
tree[root*+].value+=(end-mid)*tree[root].add;
tree[root*].add+=tree[root].add;
tree[root*+].add+=tree[root].add;
tree[root].add=;
}
void update(ll root,ll start,ll end,ll l,ll r,ll k){
if(r<start||l>end) return ;
if(start>=l&&end<=r){
tree[root].value+=k*(end-start+);
tree[root].add+=k;
return ;
}
pushdown(root,start,end);
ll mid=(start+end)/;
update(root*,start,mid,l,r,k);
update(root*+,mid+,end,l,r,k);
tree[root].value=tree[root*].value+tree[root*+].value;
return ;
} ll query(ll root,ll start,ll end,ll i){
if(start==end) {
if(end==i) return tree[root].value;
}
if(start>i||i>end) return ;
pushdown(root,start,end);
ll mid=(start+end)/;
return query(root*,start,mid,i)+query(root*+,mid+,end,i);
} int main()
{
ios::sync_with_stdio();
ll n,m,q;
cin>>n>>m>>q;
for(ll i=;i<=n;i++) cin>>arr[i];
for(ll i=;i<=m;i++) cin>>l1[i]>>r1[i]>>v[i];
bt(,,n);
// for(ll i=1;i<=3*n;i++) cout<<tree[i].value<<endl;
for(ll i=;i<=q;i++){
ll x,y;
cin>>x>>y;
tt[x]++;
tt[y+]--;
}
ll tmp=;
for(ll i=;i<=m;i++){
tmp+=tt[i];
cnt[i]=tmp;
}
for(ll i=;i<=m;i++){
update(,,n,l1[i],r1[i],cnt[i]*v[i]);
}
for(ll i=;i<=n;i++) cout<<query(,,n,i)<<" ";
return ;
}

最新文章

  1. LPC1769 CAN的自测试模式
  2. EF架构~在T4模版中为所有属性加默认值
  3. jquery操作常用HTML控件
  4. 2.1:你的第一个AngularJS App
  5. [原创]cocos2d-x + Lua接入iOS原生SDK的实现方案
  6. sql 自定义函数-16进制转10进制
  7. 【译】 AWK教程指南 附录E-正则表达式
  8. 解决VS2008打开假死或者打开设计模式假死的问题
  9. jquery mobile script
  10. OC语言-01类和对象
  11. DataTables获取表单输入框数据
  12. MFC 在对话框显示图片的多种方法
  13. eclipse中如何同期化
  14. Prometheus安装和配置node_exporter监控主机
  15. ArcGIS 批量修改数据名称-arcgis案例实习教程
  16. yapi部署文档
  17. iOS进阶学习笔记
  18. Cannot create container for service peer1.org2.example.com: Conflict. 解决方案
  19. Elasticsearch--&gt;Get Started--&gt;Exploring Your Cluster
  20. flask_模板

热门文章

  1. vnpy源码阅读学习(7):串在一起
  2. 修改imx6ull开机LOGO(一)
  3. JSP(一)----入门学习
  4. Smallest Range II
  5. 家乐的深度学习笔记「4」 - softmax回归
  6. Ubuntu 18.04 将gcc版本降级为5.5版本
  7. 使用PyTorch进行迁移学习
  8. jQuery的层级选择器
  9. 监控一哥Prometheus你可认识?
  10. RHCS概述