社区讨论

好奇怪,为什么查询数据会改变数组的值

P1471方差参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@loi5tnpy
此快照首次捕获于
2023/11/03 13:13
2 年前
此快照最后确认于
2023/11/03 16:42
2 年前
查看原帖
CPP
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;

#define N 100010
#define LL double
#define lc u<<1   //乘二  
#define rc u<<1|1 //乘二+1
#define ll long long

LL w[N];

struct Tree
{
	ll l,r;
	LL sum,add;     //线段树
}tr1[N*4],tr2[N*4];

void pushup(ll u){      //上传     (父节点)
	tr1[u].sum=tr1[lc].sum+tr1[rc].sum;
	tr2[u].sum=tr2[lc].sum+tr2[rc].sum;
}

void pushdown(ll u)    //往下传    (父节点)
{
	if(tr1[u].add)
	{
		tr1[lc].sum+=tr1[u].add*(tr1[lc].r-tr1[lc].l+1);
		tr1[rc].sum+=tr1[u].add*(tr1[rc].r-tr1[rc].l+1);
		tr1[lc].add+=tr1[u].add;
		tr1[rc].add+=tr1[u].add;
		tr1[u].add=0;
	}
	if(tr2[u].add)
	{
		tr2[lc].sum+=2*tr2[u].add*tr1[u].sum+(tr2[lc].r-tr2[lc].l+1)*tr2[u].add*tr2[u].add;
		tr2[rc].sum+=2*tr2[u].add*tr1[u].sum+(tr2[rc].r-tr2[rc].l+1)*tr2[u].add*tr2[u].add;;
		tr2[lc].add+=tr2[u].add;
		tr2[rc].add+=tr2[u].add;
		tr2[u].add=0;
	}
}

void build1(ll u,ll l,ll r)  //建树     (父节点,左端点,右端点)  //本身
{
	tr1[u]={l,r,w[l],0};
	if(l==r) return;
	ll m=l+r>>1;   //除二
	build1(lc,l,m);
	build1(rc,m+1,r);
	pushup(u);
}

void build2(ll u,ll l,ll r)  //建树     (父节点,左端点,右端点)   //平方
{
	tr2[u]={l,r,w[l]*w[l],0};   
	if(l==r) return;
	ll m=l+r>>1;   //除二
	build2(lc,l,m);
	build2(rc,m+1,r);
	pushup(u);
}

void change(ll u,ll l,ll r,LL k)  //区间修(父节点,总左端点,总右端点,每段加多少)
{
    if(l>tr1[u].r || r<tr1[u].l) return;
	if(l<=tr1[u].l&&tr1[u].r<=r) 
	{
	    tr1[u].sum+=(tr1[u].r-tr1[u].l+1)*k;
	    tr2[u].sum+=tr1[u].sum*k*2+(tr1[u].r-tr1[u].l+1)*k*k;
	    tr1[u].add+=k;    
		tr2[u].add+=k;                     //先用懒标记存起来
		return;  //如果被全包含,直接返回
	}	
	ll m=tr1[u].l+tr1[u].r>>1;      //除二
	pushdown(u);
	if(l<=m) change(lc,l,r,k);
	if(r>m) change(rc,l,r,k);
	pushup(u);
}

LL query(Tree tree[],ll u,ll l,ll r){      //区间查找(输出)  (父节点,总左端点,总右端点)
	if(l<=tree[u].l&&tree[u].r<=r) return tree[u].sum;
	ll m=tree[u].l+tree[u].r>>1;  //除二
	pushdown(u);
	LL ans=0;
	if(l<=m) ans+=query(tree,lc,l,r);
	if(r>m) ans+=query(tree,rc,l,r);
	return ans;
}

int main()
{
	int n,m,op,x,y;
	double k;
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>w[i];
	
	

    build1(1,1,n);
    build2(1,1,n);

    while(m--)
    {
	cin>>op>>x>>y;
	if(op==2) cout<<fixed<<setprecision(4)<<query(tr1,1,x,y)/((y - x + 1) * 1.0)<<endl;
	else if(op==1) cin>>k,change(1,x,y,k);
	else cout<<fixed<<setprecision(4)<<query(tr2,1,x,y)/((y - x + 1) * 1.0)-query(tr1,1,x,y)/((y - x + 1) * 1.0)*(query(tr1,1,x,y))/((y - x + 1) * 1.0)<<endl;
	cout<<endl;
	    for(int i=1;i<=n;++i)
    {
    	cout<<tr2[i].sum<<' ';  //检查数据出错(在输入2的时候数据出错最明显)
	}
	cout<<endl;
    }

return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...