CF 295A Greg and Array (两次建树,区间更新,单点查询)

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
/*
题意:给出原始序列a[1],a[2],...a[n]
给出m个操作方式 l r d,把a[l],...a[r]都加上d
然后给出k个操作 x y 执行第x到第y个操作 思路:如果直接执行k个对应的x~y操作,会超时的。
所以,我们需要统计一下对于m个操作,每个操作需要统计多少次,然后每个操作执行一次即可。
这样就先建立一颗树,查询k次[x,y],最后再单点查询,得到第i个操作需要执行的次数cnt[i]。
然后在建立一次(因为操作都一样,所以用同一棵树即可),这次分别对m个操作进行更新,
更新值为cnt[i]*di,再单点更新得出最后的a[i]。
*/
using namespace std;
const int maxn=;
int n,m,k;
long long a[maxn]; //原始序列
long long cnt[maxn]; //cnt[i]表示第i个操作方式需要执行的次数
struct Node{
long long add;
bool lazy;
}tree[maxn<<]; struct Operation{
int l,r;
long long d;
}op[maxn]; void build(int rt,int L,int R){
tree[rt].add=;
tree[rt].lazy=false;
if(L==R)
return;
int mid=(L+R)>>;
build(lson);
build(rson);
} void pushDown(int rt){
if(tree[rt].lazy){
tree[rt<<].add+=tree[rt].add;
tree[rt<<|].add+=tree[rt].add;
tree[rt<<].lazy=tree[rt<<|].lazy=true;
tree[rt].add=;
tree[rt].lazy=false;
}
}
void update(int rt,int L,int R,int l,int r,long long val){
if(l<=L&&R<=r){
tree[rt].add+=val;
tree[rt].lazy=true;
return;
}
pushDown(rt);
int mid=(L+R)>>;
if(l<=mid)
update(lson,l,r,val);
if(r>mid)
update(rson,l,r,val);
} //单点查询cnt
void query1(int rt,int L,int R){
if(L==R){
cnt[L]+=tree[rt].add;
return;
}
pushDown(rt);
int mid=(L+R)>>;
query1(lson);
query1(rson);
}
//单点查询a
void query2(int rt,int L,int R){
if(L==R){
a[L]+=tree[rt].add;
return;
}
pushDown(rt);
int mid=(L+R)>>;
query2(lson);
query2(rson);
}
int main()
{
int x,y;
scanf("%d%d%d",&n,&m,&k); for(int i=;i<=n;i++){
scanf("%I64d",&a[i]);
}
for(int i=;i<=m;i++){
scanf("%d%d%I64d",&op[i].l,&op[i].r,&op[i].d);
}
//先对m个操作方式建树,统计每个操作方式需要执行的次数
build(,,m);
for(int i=;i<=k;i++){
scanf("%d%d",&x,&y);
update(,,m,x,y,); }
memset(cnt,,sizeof(cnt));
query1(,,m); //再对n个数建树,更新所增加的值
build(,,n);
for(int i=;i<=m;i++){
update(,,n,op[i].l,op[i].r,op[i].d*cnt[i]); //对每个操作只要查询一次即可
}
query2(,,n);
flag=true;
for(int i=;i<=n;i++){
if(flag){
printf("%I64d",a[i]);
flag=false;
}
else
printf(" %I64d",a[i]);
}
printf("\n");
return ;
}
上一篇:愉快且方便的处理时间-- LocalDate


下一篇:LinearRegressionWithRegularization