社区讨论
query不输出求条
P3372【模板】线段树 1参与者 4已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mjp2x9tj
- 此快照首次捕获于
- 2025/12/28 09:57 2 个月前
- 此快照最后确认于
- 2025/12/31 12:50 2 个月前
CPP
#include<bits/stdc++.h>
#define I_don_t_want_to_AFO int main()
#define I_want_to_study_OI_forever return 0;
using namespace std;
long long n,m,a[100005];
struct node{
int l,r;
long long val,tag;
}tr[400005];
void push_up(int u){
tr[u].val=tr[u<<1].val+tr[u<<1|1].val;
}
void push_down(int u){
if(tr[u].tag){
tr[u<<1].val+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].tag;
tr[u<<1].tag+=tr[u].tag;
tr[u<<1|1].val+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].tag;
tr[u<<1|1].tag+=tr[u].tag;
tr[u].tag=0;
}
}
void build(int u,int l,int r){
tr[u].l=l;
tr[u].r=r;
tr[u].tag=0;
if(l==r){
tr[u].val=a[u];
return;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
push_up(u);
}
long long query(int u,int ql,int qr){
cout<<u<<" "<<"123456789123456789123456789\n";
if(tr[u].l>=ql&&tr[u].r<=qr){
return tr[u].val;
}
push_down(u);
int mid=tr[u].l+tr[u].r>>1;
long long res=0;
if(ql<=mid){
res+=query(u<<1,ql,qr);
}
if(qr>mid){
res+=query(u<<1|1,ql,qr);
}
return res;
}
void change(int u,int ql,int qr,int d){
if(tr[u].l>=ql&&tr[u].r<=qr){
tr[u].val+=(tr[u].r-tr[u].l+1)*d;
tr[u].tag+=d;
}
push_down(u);
int mid=tr[u].l+tr[u].r>>1;
if(ql<=mid){
change(u<<1,ql,qr,d);
}
if(qr>mid){
change(u<<1|1,ql,qr,d);
}
push_up(u);
}
I_don_t_want_to_AFO{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
// cout<<"3112";
while(m--){
int op,x,y,z;
cin>>op>>x>>y;
if(op==1){
cin>>z;
change(1,x,y,z);
}else{
cout<<query(1,x,y);
}
}
I_want_to_study_OI_forever
}
rt
回复
共 11 条回复,欢迎继续交流。
正在加载回复...