qige_mingzi @ 2023-10-20 16:19:02
RT，WA on # 2-10 评测记录
#include<bits/stdc++.h>
#define int long long
#define mid (l+r)/2
#define ls x<<1
#define rs (x<<1)|1
using namespace std;
int n,m;
const int maxn = 1e5+100;
int a[maxn];
int t[maxn<<2],tag[maxn<<2];
void pushup(int x){
x >>= 1;
while(x){
t[x] = t[ls]+t[rs];
x >>= 1;
}
}
void pushdown(int x,int l,int r){
t[ls] += (mid-l+1)*tag[x];
tag[ls] += tag[x];
t[rs] += (r-mid)*tag[x];
tag[rs] += tag[x];
tag[x] = 0;
}
void build(int l,int r,int x){
if(l == r){
//cout << l << " " << a[l] << " " << x << endl;
t[x] = a[l];
pushup(x);
return;
}
build(l,mid,ls);
build(mid+1,r,rs);
}
void add(int l,int r,int ql,int qr,int k,int x){
if(l >= ql&&r <= qr){
tag[x] += k;
t[x] += k*(r-l+1);
pushup(x);
return;
}
if(ql <= mid){
add(l,mid,ql,qr,k,ls);
}
if(qr > mid){
add(mid+1,r,ql,qr,k,rs);
}
}
int query(int l,int r,int ql,int qr,int x){
if(l >= ql&&r <= qr){
return t[x];
}
if(r < ql||l > qr){
return 0;
}
pushdown(x,l,r);
return query(l,mid,ql,qr,ls)+query(mid+1,r,ql,qr,rs);
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin >> n >> m;
for(int i = 1;i <= n;i++){
scanf("%lld",&a[i]);
}
build(1,n,1);
/*for(int i = 1;i <= n<<2;i++){
cout << t[i] << ' ';
}*/
int opt,l,r,k;
for(int i = 1;i <= m;i++){
scanf("%lld",&opt);
if(opt == 1){
scanf("%lld%lld%lld",&l,&r,&k);
add(1,n,l,r,k,1);
}
else{
scanf("%lld%lld",&l,&r);
cout << query(1,n,l,r,1) << '\n';
}
}
return 0;
}
/*
Author: qige_mingzi
Start thinking at
Start coding at
Finish coding at
Finish debugging at
*/
by emo_male_god @ 2023-10-20 16:45:30
我最先看到的错误：在 build 函数里面，push_up 是放到最后的，而不是在 if 判断里面
by emo_male_god @ 2023-10-20 16:49:36
add 函数中的 push_up 操作也是要放在最后query 函数中也需要像在 add 函数中判断 qr，ql，mid 的大小关系by emo_male_god @ 2023-10-20 16:50:04
@qige_mingzi
by sdyzpf @ 2023-10-20 17:02:01
#include<bits/stdc++.h>
#define int long long
#define mid (l+r)/2
#define ls x<<1
#define rs (x<<1)|1
using namespace std;
int n,m;
const int maxn = 1e5+100;
int a[maxn];
int t[maxn<<2],tag[maxn<<2];
void pushup(int x){
x >>= 1;
while(x){
t[x] = t[ls]+t[rs];
x >>= 1;
}
}
void pushdown(int x,int l,int r){
t[ls] += (mid-l+1)*tag[x];
tag[ls] += tag[x];
t[rs] += (r-mid)*tag[x];
tag[rs] += tag[x];
tag[x] = 0;
}
void build(int l,int r,int x){
if(l == r){
//cout << l << " " << a[l] << " " << x << endl;
t[x] = a[l];
pushup(x);
return;
}
build(l,mid,ls);
build(mid+1,r,rs);
}
void add(int l,int r,int ql,int qr,int k,int x){
if(l >= ql&&r <= qr){
tag[x] += k;
t[x] += k*(r-l+1);
pushup(x);
return;
}
pushdown(x,l,r);
if(ql <= mid){
add(l,mid,ql,qr,k,ls);
}
if(qr > mid){
add(mid+1,r,ql,qr,k,rs);
}
}
int query(int l,int r,int ql,int qr,int x){
if(l >= ql&&r <= qr){
return t[x];
}
if(r < ql||l > qr){
return 0;
}
pushdown(x,l,r);
return query(l,mid,ql,qr,ls)+query(mid+1,r,ql,qr,rs);
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin >> n >> m;
for(int i = 1;i <= n;i++){
scanf("%lld",&a[i]);
}
build(1,n,1);
/*for(int i = 1;i <= n<<2;i++){
cout << t[i] << ' ';
}*/
int opt,l,r,k;
for(int i = 1;i <= m;i++){
scanf("%lld",&opt);
if(opt == 1){
scanf("%lld%lld%lld",&l,&r,&k);
add(1,n,l,r,k,1);
}
else{
scanf("%lld%lld",&l,&r);
cout << query(1,n,l,r,1) << '\n';
}
}
return 0;
}
/*
Author: qige_mingzi
Start thinking at
Start coding at
Finish coding at
Finish debugging at
*/
by sdyzpf @ 2023-10-20 17:02:52
@sdyzpf 只有一个错误，add函数里没pushup
by sdyzpf @ 2023-10-20 17:04:04
@emo_male_god 他这个写法这么写没问题。
by emo_male_god @ 2023-10-20 17:15:02
@sdyzpf 哦哦，没注意 push_up 是这样写的
by qige_mingzi @ 2023-10-20 17:18:30
@emo_male_god @sdyzpf 感谢大佬
by qige_mingzi @ 2023-10-20 17:19:02
已过，此贴完结。