社区讨论
好奇怪,为什么查询数据会改变数组的值
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 条回复,欢迎继续交流。
正在加载回复...