#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;
}
}
我估计是犯了个唐诗的错误,但我没看出来
@little_zxh_qwq O.O就是说它的询问区间不一定是一个完整的线段的,但是这个程序无法处理这种情况
@little_zxh_qwqpushdown 函数并没有正确更新子节点,而是直接修改了当前节点。此外,pushdown 函数的参数 x 应该是当前节点的标记值,而不是区间长度乘 x。 query 函数中还需要处理区间查询的逻辑。 build 函数中,lc[i] 和 rc[i] 的赋值应该在递归调用之前进行,而不是在递归调用之后。 main 函数中,pushdown 的调用方式不正确。应在更新区间时调用 pushdown ,而不是查询时。
而且到一个完整区间就停止的做法是不正确的,因为在之后的查询中可能会查询这个完整区间的子区间,你标记对于答案的影响没有正确地实施
@little_zxh_qwq 你这个就是标记永久化啊,和我的写法一样
@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;
}
@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;
}
@SerenityWay tql %%%% orz
原来是标记永久化,,,
那最好别用 pushdown 这个名字