第一次,漏洞百出,被我的同学痛批了一顿@cachejtt
#include<bits/stdc++.h>
#define ll long long
#define int ll
const int N=1e6+7;
using namespace std;
int a[N],lazy[4*N];
int n,m;
int i,j=0,x,y,k,op;
struct hhh
{
int l,r,ans;
} v[4*N];
void pushup(int x)
{
v[x].ans=v[2*x].ans+v[2*x+1].ans;
}
void build(int x,int s,int t)
{
v[x].l=s;
v[x].r=t;
if(s==t)
{
// v[x].ans=a[x];没有理解x与s==t的关系
v[x].ans=a[s];
return ;
}
int mid=(s+t)/2;
// v[2*x].l=s; v[2*x+1].r=mid;
// v[2*x+1].l=mid+1; v[2*x+1].r=t;
// 没有修改v[1]
// build(mid-s+1,s,mid);
// build(t-mid,mid,t);
// 左右端点不清楚
build(2*x,s,mid);
build(2*x+1,mid+1,t);
pushup(x);
}
void pushdown(int x)
{
if(lazy[x])
{
lazy[2*x]+=lazy[x];
lazy[2*x+1]+=lazy[x];
int mid=(v[x].l+v[x].r)/2;
// v[2*x].ans+=lazy[2*x]*lazy[2*x];
// v[2*x+1].ans+=lazy[2*x+1]*lazy[2*x+1];
// 对ywx讲的下传lazy[x]没有理解,没有理解lazy数组的含义
v[2*x].ans+=lazy[x]*(mid-v[x].l+1);
v[2*x+1].ans+=lazy[x]*(v[x].r-mid);
lazy[x]=0;
}
}
void add(int x,int s,int t,int k)
{
// cout<<"x:"<<x<<endl;
// cout<<"l:"<<v[x].l<<" r:"<<v[x].r<<endl;
//用于检验正确性与死循环。
if(v[x].l>=s&&v[x].r<=t)
{
v[x].ans+=k*(v[x].r-v[x].l+1);
lazy[x]+=k;
return ;
}
pushdown(x);
int mid=(v[x].l+v[x].r)/2;
// add(2*x,v[x].l,mid,k);
// add(2*x+1,mid,v[x].r,k);
// 不清楚左右端点,还和自己s,t的定义自相矛盾
// 同时没有注意到修改是有条件的 ,两个和mid有关的if没写
if(mid>=s)add(2*x,s,t,k);
if(mid+1<=t)add(2*x+1,s,t,k);
// 忘记上传。
pushup(x);
}
int q(int x,int s,int t)
{
// cout<<"x:"<<x<<endl;
// cout<<"l:"<<v[x].l<<" r:"<<v[x].r<<endl;
//用于检验正确性与死循环。发现死循环了,意识到mid的值不对
if(v[x].l>=s&&v[x].r<=t)//这个家伙还把小于号写成大于号,难绷
{
return v[x].ans;
}
pushdown(x);
int mid=(v[x].l+v[x].r)/2,sum=0;
// sum+=q(2*x,v[x].l,mid);
// sum+=q(2*x+1,mid+1,v[x].r);
// 对s,t的定义自相矛盾
// 忘记下传。
if(mid>=s)sum+=q(2*x,s,t);
if(mid+1<=t)sum+=q(2*x+1,s,t);
return sum;
}
signed main()
{
cin>>n>>m;
for(i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
// for(i=1;i<=4*n;i++){
// cout<<"v["<<i<<"].ans="<<v[i].ans<<endl;
// cout<<"l:"<<v[i].l<<" r:"<<v[i].r<<endl;
// }
// 用于检验建树是否正确。
for(i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
add(1,x,y,k);
// for(int kk=1;kk<=n;kk++){
// cout<<"a["<<kk<<"]="<<q(1,kk,kk)<<" ";
// }
// cout<<endl;
//用于检验add的正确性
}
else
{
// j++;
// 这个家伙想要最后输出
cin>>x>>y;
cout<<q(1,x,y)<<endl;
}
}
// for(i=1;i<=m;i++) cout<<anss[i]<<endl;
// 但是却搞混了j和m的关系
return 0;
}
不服气的我又再写了一次
#include<bits/stdc++.h>
#define ll long long
#define int ll
const int N=1e6+7;
using namespace std;
int a[N],lazy[4*N];
int n,m,i,x,y,k,op;
struct hhh
{
int l,r,ans;
} v[4*N];
void pushup(int x)
{
v[x].ans=v[2*x].ans+v[2*x+1].ans;
}
void build(int x,int s,int t)
{
v[x].l=s;
v[x].r=t;
if(s==t)
{
v[x].ans=a[s];
return ;
}
int mid=(s+t)/2;
build(2*x,s,mid);
build(2*x+1,mid+1,t);
pushup(x);
}
void pushdown(int x)
{
if(lazy[x])
{
lazy[2*x]+=lazy[x];
lazy[2*x+1]+=lazy[x];
int mid=(v[x].l+v[x].r)/2;
v[2*x].ans+=lazy[x]*(mid-v[x].l+1);
v[2*x+1].ans+=lazy[x]*(v[x].r-mid);
lazy[x]=0;
}
}
void add(int x,int s,int t,int k)
{
if(v[x].l>=s&&v[x].r<=t)
{
v[x].ans+=k*(v[x].r-v[x].l+1);
lazy[x]+=k;
return ;
}
pushdown(x);
int mid=(v[x].l+v[x].r)/2;
if(mid>=s)add(2*x,s,t,k);
if(mid+1<=t)add(2*x+1,s,t,k);
pushup(x);
}
int q(int x,int s,int t)
{
if(v[x].l>=s&&v[x].r<=t)
{
return v[x].ans;
}
pushdown(x);
int mid=(v[x].l+v[x].r)/2,sum=0;
if(mid>=s)sum+=q(2*x,s,t);
if(mid+1<=t)sum+=q(2*x+1,s,t);
return sum;
}
signed main()
{
cin>>n>>m;
for(i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
add(1,x,y,k);
}
else
{
cin>>x>>y;
cout<<q(1,x,y)<<endl;
}
}
return 0;
}
完美通过,然后我又开始作了,去掉了结构体,加了两个状态
#include<bits/stdc++.h>
#define ll long long
#define int ll
const int N=1e6+7;
int n,m,i,x,y,op,k;
int v[4*N],lazy[4*N],a[N];
using namespace std;
void pushup(int x)
{
v[x]=v[2*x]+v[2*x+1];
}
void build(int x,int s,int t)
{
if(s==t)
{
v[x]=a[s];
return ;
}
int mid=(s+t)/2;
build(2*x,s,mid);
build(2*x+1,mid+1,t);
pushup(x);
}
void pushdown(int x,int l,int r)
{
if(lazy[x])
{
lazy[2*x]+=lazy[x];
lazy[2*x+1]+=lazy[x];
int mid=l+r>>1;
v[2*x]+=lazy[2*x]*(mid-l+1);
v[2*x+1]+=lazy[2*x+1]*(r-mid);
lazy[x]=0;
}
}
void add(int x,int l,int r,int s,int t,int k)
{
if(s>=l&&t<=r)
{
v[x]+=k*(t-s+1);
lazy[x]+=k;
return ;
}
pushdown(x,s,t);
int mid=s+t>>1;
if(mid>=l) add(2*x,l,r,s,mid,k);
if(mid<r) add(2*x+1,l,r,mid+1,t,k);
pushup(x);
}
int q(int x,int l,int r,int s,int t)//l,r是待查 s,t是当前
{
if(s>=l&&t<=r)
{
return v[x];
}
pushdown(x,s,t);
int mid=s+t>>1,sum=0;
if(mid>=l) sum+=q(2*x,l,r,s,mid);
if(mid<r) sum+=q(2*x+1,l,r,mid+1,t);
return sum;
}
signed main()
{
cin>>n>>m;
for(i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(i=1;i<=m;i++)
{
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
add(1,x,y,1,n,k);
}
else
{
cin>>x>>y;
cout<<q(1,x,y,1,n)<<endl;
}
}
return 0;
}
过了一个点,对着AC的代码对比了半天,还用上了https://csacademy.com/app/diffing_tool/ 对比,看了一个小时,最终在两位大佬的帮助下发现了
void pushdown(int x,int l,int r)
{
if(lazy[x])
{
lazy[2*x]+=lazy[x];
lazy[2*x+1]+=lazy[x];
int mid=l+r>>1;
v[2*x]+=lazy[2*x]*(mid-l+1);
v[2*x+1]+=lazy[2*x+1]*(r-mid);
lazy[x]=0;
}
}
应该改成
v[2*x]+=lazy[x]*(mid-l+1);
v[2*x+1]+=lazy[x]*(r-mid);
感谢 VAN♂游戏 和 IhpEcVns 两位大佬的帮助 让我懂得了:作妖有风险,爆零两行泪