社区讨论

哪位大佬帮忙看看,谢谢!!!!

P3372【模板】线段树 1参与者 5已保存回复 8

讨论操作

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

当前回复
8 条
当前快照
1 份
快照标识符
@mi7yp65d
此快照首次捕获于
2025/11/21 05:47
4 个月前
此快照最后确认于
2025/11/21 05:47
4 个月前
查看原帖
#include #include #include #include using namespace std; int n,m; long long int a[100010]; const int maxn=100010; struct segtreenode{ long long int val,lazytag; }segtree[4maxn]; void build(long long int rt,long long int al,long long int ar) { segtree[rt].lazytag=0; if(al==ar) { segtree[rt].val=a[al]; return ; } long long int m=(al+ar)/2; build(rt2,al,m); build(rt2+1,m+1,ar); segtree[rt].val=segtree[rt2].val+segtree[rt2+1].val; }//建树 void pushdown(long long int rt,long long int al,long long int ar) { long long int m=(al+ar)/2; if(segtree[rt].lazytag!=0) { segtree[rt2].val+=segtree[rt].lazytag*(m-al+1); segtree[rt2+1].val+=segtree[rt].lazytag(ar-m+1+1); segtree[rt2].lazytag+=segtree[rt].lazytag; segtree[rt2+1].lazytag+=segtree[rt].lazytag; segtree[rt].lazytag=0; } } void updata(long long int rt,long long int al,long long int ar,long long int ql,long long int qr,long long int val) { if(al>qr||ar<ql) return; if(al>=ql&&ar<=qr) { segtree[rt].val+=(val*(ar-al+1)); segtree[rt].lazytag+=val; return; } pushdown(rt,al,ar); long long int m=(al+ar)/2; updata(rt2,al,m,ql,qr,val); updata(rt2+1,m+1,ar,ql,qr,val); segtree[rt].val=segtree[rt2].val+segtree[rt2+1].val; return;//增加一个值 } long long int ans=0; long long int query(long long int rt,long long int al,long long int ar,long long int ql,long long int qr)//查询 { if(al>qr||ar<ql) return 0; if(al>=ql&&ar<=qr) { return segtree[rt].val; } pushdown(rt,al,ar); long long int m=(al+ar)/2; return query(rt2,al,m,ql,qr)+query(rt2+1,m+1,ar,ql,qr); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%lld",&a[i]); } build(1,1,n); for(int i=1;i<=m;++i) { int num; scanf("%d",&num); if(num==1) { long long int ql,qr,val; scanf("%lld%lld%lld",&ql,&qr,&val); updata(1,1,n,ql,qr,val);; } if(num==2) { ans=0; long long int ql,qr; scanf("%lld%lld",&ql,&qr); ans=query(1,1,n,ql,qr); printf("%lld\n",ans); } } return 0; }

回复

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

正在加载回复...