求调
- 板块P3372 【模板】线段树 1
- 楼主little_zxh_qwq
- 当前回复46
- 已保存回复48
- 发布时间2025/2/6 20:30
- 上次更新2025/2/6 20:58:32
查看原帖
被骇客银狼阻止的越权访问保存失败
求调
#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;
}
}
我估计是犯了个唐诗的错误，但我没看出来
_LRH_2025/2/6 20:39
@little_zxh_qwq 呜呜呜姐姐你看看我前面的啊
_X_Z_N_2025/2/6 20:40
lazy是tag
Ew_Cors2025/2/6 20:40
@little_zxh_qwq 什么叫 “最多传树的深度次”，
SerenityWay2025/2/6 20:41
pushdown 函数并没有正确更新子节点，而是直接修改了当前节点。此外，pushdown 函数的参数 x 应该是当前节点的标记值，而不是区间长度乘 x。 query 函数中还需要处理区间查询的逻辑。 build 函数中，lc[i] 和 rc[i] 的赋值应该在递归调用之前进行，而不是在递归调用之后。 main 函数中，pushdown 的调用方式不正确。应在更新区间时调用 pushdown ，而不是查询时。
Ew_Cors2025/2/6 20:41
你的 pushdown 写法本来就有问题，你需要重新理解线段树的 tag 和 pushdown 的机制
@Ew_Cors有完整的区间的话就不下传了
@LRH 没看懂qaq
_X_Z_N_2025/2/6 20:42
我的呢，用的标记永久化
#include<bits/stdc++.h>
using namespace std;
struct node
{
long long lb,rb;
long long s;
long long lazy;
};
node tree[400005];
long long num[100005];
void build(long long r,long long x,long long y)
{
tree[r].lb=x;
tree[r].rb=y;
tree[r].lazy=0;
if(x==y)
{
tree[r].s=num[x];
return;
}
long long mid=(x+y)/2;
build(r<<1,x,mid);
build((r<<1)+1,mid+1,y);
tree[r].s=tree[r<<1].s+tree[(r<<1)+1].s;
return;
}
void change(long long r,long long x,long long y,long long d)
{
if(x<=tree[r].lb && tree[r].rb<=y)
{
tree[r].lazy+=d;
return;
}
tree[r].s+=(min(tree[r].rb,y)-max(tree[r].lb,x)+1)*d;
long long mid=(tree[r].lb+tree[r].rb)/2;
if(x<=mid)
{
change(r<<1,x,y,d);
}
if(y>mid)
{
change((r<<1)+1,x,y,d);
}
return;
}
long long findsum(long long r,long long x,long long y)
{
if(x<=tree[r].lb && tree[r].rb<=y)
{
return tree[r].s+(tree[r].rb-tree[r].lb+1)*tree[r].lazy;
}
long long ans=(min(tree[r].rb,y)-max(tree[r].lb,x)+1)*tree[r].lazy;
long long mid=(tree[r].lb+tree[r].rb)/2;
if(x<=mid)
{
ans+=findsum(r<<1,x,y);
}
if(y>mid)
{
ans+=findsum((r<<1)+1,x,y);
}
return ans;
}
int main()
{
long long n,m;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",num+i);
}
build(1,1,n);
for(int i=1;i<=m;i++)
{
int aa;
cin>>aa;
if(aa==1)
{
long long x,y,k;
scanf("%lld %lld %lld",&x,&y,&k);
change(1,x,y,k);
}
if(aa==2)
{
long long x,y;
scanf("%lld %lld",&x,&y);
printf("%lld\n",findsum(1,x,y));
}
}
return 0;
}
Ew_Cors2025/2/6 20:42
@little_zxh_qwq 哦确实，
Ew_Cors2025/2/6 20:44
但是 pushdown 只需要把当前节点的标记下放到儿子节点就行了，不需要递归