此贴仅以警示后人!!!
查看原帖
此贴仅以警示后人!!!
698678
zlinda楼主2022/7/26 19:54

第一次,漏洞百出,被我的同学痛批了一顿@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 两位大佬的帮助 让我懂得了:作妖有风险,爆零两行泪

2022/7/26 19:54
加载中...