G - Greg and Array CodeForces - 296C 差分+线段树
2024-10-09 00:41:21
题目大意:输入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 ;
}
最新文章
- LPC1769 CAN的自测试模式
- EF架构~在T4模版中为所有属性加默认值
- jquery操作常用HTML控件
- 2.1:你的第一个AngularJS App
- [原创]cocos2d-x + Lua接入iOS原生SDK的实现方案
- sql 自定义函数-16进制转10进制
- 【译】 AWK教程指南 附录E-正则表达式
- 解决VS2008打开假死或者打开设计模式假死的问题
- jquery mobile script
- OC语言-01类和对象
- DataTables获取表单输入框数据
- MFC 在对话框显示图片的多种方法
- eclipse中如何同期化
- Prometheus安装和配置node_exporter监控主机
- ArcGIS 批量修改数据名称-arcgis案例实习教程
- yapi部署文档
- iOS进阶学习笔记
- Cannot create container for service peer1.org2.example.com: Conflict. 解决方案
- Elasticsearch-->;Get Started-->;Exploring Your Cluster
- flask_模板