求调
查看原帖
求调
1603819
little_zxh_qwq楼主2025/2/6 20:30
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[114514];
int sgt[414514];
int lc[414514],rc[414514];
int tag[414514];
int build(int l,int r,int i){
	lc[i]=l;
	rc[i]=r;
	if(l==r){
		sgt[i]=a[l];
		return a[l];
	}
	int m=(l+r)>>1;
	sgt[i]=build(l,m,i<<1)+build(m+1,r,(i<<1)|1);
	return sgt[i];
}
void pushdown(int l,int r,int i,int x){
	if(l==lc[i]&&r==rc[i]){
		tag[i]+=(r-l+1)*x;
		sgt[i]+=tag[i];
		return;
	}
	int m=rc[i*2];
	if(l<=m){
		pushdown(l,m,i<<1,x);
	}
	if(r>=m+1){
		pushdown(m+1,r,(i<<1)|1,x);
	}
}
int query(int l,int r,int i){
	if(l==lc[i]&&r==rc[i]){
		return sgt[i];
	}
	int m=rc[i*2];
	if(tag[i]){
		sgt[i]+=tag[i];
		pushdown(lc[i<<1],rc[i<<1],i<<1,tag[i]/(rc[i]-lc[i]+1));
		pushdown(lc[(i<<1)|1],rc[(i<<1)|1],(i<<1)|1,tag[i]/(rc[i]-lc[i]+1));
		tag[i]=0;
	}
	int sum=0;
	if(l<=m){
		sum+=query(l,m,i<<1);
	}
	if(r>=m+1){
		sum+=query(m+1,r,(i<<1)|1);
	}
	return sum;
}
main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int t=build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1){
			int x;
			cin>>x;
			pushdown(l,r,1,x);
		}
		else{
			cout<<query(l,r,1)<<endl;
		}
	}
	for(int i=1;i<=n*4;i++){
		cout<<i<<" "<<lc[i]<<" "<<rc[i]<<" "<<tag[i]<<" "<<sgt[i]<<endl;
	}
} 

我估计是犯了个唐诗的错误,但我没看出来

2025/2/6 20:30
1603819
little_zxh_qwq楼主2025/2/6 20:44

@Ew_Cors

虽然但是我的pushdown好像并不是pushdown,我的pushdown的意思是把这段区间传下去,类似于求和时,把所有这样的区间加上tag,而且我的tag存的是这个区间一共变化了多少,写的方法可能比较奇特

2025/2/6 20:44
661573
_LRH_2025/2/6 20:45

@little_zxh_qwq O.O就是说它的询问区间不一定是一个完整的线段的,但是这个程序无法处理这种情况

2025/2/6 20:45
1048165
SerenityWay2025/2/6 20:45

@little_zxh_qwqpushdown 函数并没有正确更新子节点,而是直接修改了当前节点。此外,pushdown 函数的参数 x 应该是当前节点的标记值,而不是区间长度乘 x。 query 函数中还需要处理区间查询的逻辑。 build 函数中,lc[i] 和 rc[i] 的赋值应该在递归调用之前进行,而不是在递归调用之后。 main 函数中,pushdown 的调用方式不正确。应在更新区间时调用 pushdown ,而不是查询时。

2025/2/6 20:45
180103
Ew_Cors2025/2/6 20:45

而且到一个完整区间就停止的做法是不正确的,因为在之后的查询中可能会查询这个完整区间的子区间,你标记对于答案的影响没有正确地实施

2025/2/6 20:45
1392543
_X_Z_N_2025/2/6 20:45

@little_zxh_qwq 你这个就是标记永久化啊,和我的写法一样

2025/2/6 20:45
1048165
SerenityWay2025/2/6 20:46

@little_zxh_qwq附代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int a[MAXN];
int sgt[MAXN];
int lc[MAXN*4],rc[MAXN*4];
int tag[MAXN*4];
void pushdown(int i){
	if(tag[i]){
		sgt[i<<1]+=tag[i]*(rc[i<<1]-lc[i<<1]+1);
		sgt[(i<<1)|1]+=tag[i]*(rc[(i<<1)|1]-lc[(i<<1)|1]+1);
		tag[i<<1]+=tag[i];
		tag[(i<<1)|1]+=tag[i];
		tag[i]=0;
	}
}
void build(int l,int r,int i){
	lc[i]=l;
	rc[i]=r;
	if(l==r){
		sgt[i]=a[l];
		return;
	}
	int m=(l+r)>>1;
	build(l,m,i<<1);
	build(m+1,r,(i<<1)|1);
	sgt[i]=sgt[i<<1]+sgt[(i<<1)|1];
}

void update(int l,int r,int i,int x){
	if(l<=lc[i]&&rc[i]<=r){
		sgt[i]+=x*(rc[i]-lc[i]+1);
		tag[i]+=x;
		return;
	}
	pushdown(i);
	int m=(lc[i]+rc[i])>>1;
	if(l<=m) update(l,r,i<<1,x);
	if(r>m) update(l,r,(i<<1)|1,x);
	sgt[i]=sgt[i<<1]+sgt[(i<<1)|1];
}
int query(int l,int r,int i){
	if(l<=lc[i]&&rc[i]<=r){
		return sgt[i];
	}
	pushdown(i);
	int m=(lc[i]+rc[i])>>1;
	int sum=0;
	if(l<=m) sum+=query(l,r,i<<1);
	if(r>m) sum+=query(l,r,(i<<1)|1);
	return sum;
}
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1){
			int x;
			cin>>x;
			update(l,r,1,x);
		}else{
			cout<<query(l,r,1)<<endl;
		}
	}
	return 0;
}
2025/2/6 20:46
1603819
little_zxh_qwq楼主2025/2/6 20:46

@Ew_Cors 我推下去了啊,

if(tag[i]){
		sgt[i]+=tag[i];
		pushdown(lc[i<<1],rc[i<<1],i<<1,tag[i]/(rc[i]-lc[i]+1));
		pushdown(lc[(i<<1)|1],rc[(i<<1)|1],(i<<1)|1,tag[i]/(rc[i]-lc[i]+1));
		tag[i]=0;
	}
2025/2/6 20:46
1412938
piano_pei2025/2/6 20:46

@SerenityWay tql %%%% orz

2025/2/6 20:46
180103
Ew_Cors2025/2/6 20:46

原来是标记永久化,,,

那最好别用 pushdown 这个名字

2025/2/6 20:46
1603819
little_zxh_qwq楼主2025/2/6 20:47

所以有没有人能够在我源代码上改改?

2025/2/6 20:47