zxr_zwgh @ 2024-07-31 09:19:19
RT
#include<bits/stdc++.h>
using namespace std;
struct node{
int left,right;
int value,lazy=0;
}tree[4000005];
int a[1000005];
void build(int l,int r,int root){
tree[root].left=l,tree[root].right=r;
if(tree[root].left==tree[root].right){
tree[root].value=a[l];
return;
}
int mid=(tree[root].left+tree[root].right)/2;
build(l,mid,tree[root].left);
build(mid+1,r,tree[root].right);
tree[root].value=tree[root*2].value+tree[root*2+1].value;
}
void spread(int root){
if(tree[root].left==tree[root].right){
return;
}
int lazy=tree[root].lazy;
tree[root*2].lazy+=lazy;
tree[root*2+1].lazy+=lazy;
tree[root*2].value+=lazy*(tree[root*2].right-tree[root*2].left+1);
tree[root*2+1].value+=lazy*(tree[root*2+1].right-tree[root*2].left+1);
tree[root].lazy=0;
}
void update(int root,int l,int r,int v){
if(tree[root].left>=l&&tree[root].right<=r){
tree[root].lazy=v;
tree[root].value+=(tree[root].right-tree[root].left+1);
return;
}
spread(root);
int mid=(tree[root].left+tree[root].right)/2;
if(l<=mid) update(root*2,l,r,v);
if(r>mid) update(root*2+1,l,r,v);
tree[root].value=tree[root*2].value+tree[root*2+1].value;
}
long long query(int root,int l,int r){
long long ans=0;
if(tree[root].left>=l&&tree[root].right<=r){
return tree[root].value;
}
spread(root);
int mid=(tree[root].left+tree[root].right)/2;
if(l<=mid) ans+=query(root*2,l,r);
if(r>mid) ans+=query(root*2+1,l,r);
return ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1) ;
while(q--){
int op;
cin>>op;
if(op==1){
int l,r,v;
cin>>l>>r>>v;
update(1,l,r,v);
}else if(op==2){
int l,r;
cin>>l>>r;
cout<<query(1,l,r)<<"\n";
}
}
return 0;
}by Brilliant11001 @ 2024-07-31 09:21:35
by Brilliant11001 @ 2024-07-31 09:22:35
@zxr_zwgh
by zxr_zwgh @ 2024-07-31 09:27:33
@Brilliant11001 拜谢qwq,已关
不过改了还是不对
by Brilliant11001 @ 2024-07-31 09:29:31
by zxr_zwgh @ 2024-07-31 09:32:55
@Brilliant11001 e,错了一堆，不过感觉应该是建树或查询的问题，因为没有输出
by Brilliant11001 @ 2024-07-31 09:34:55
by zxr_zwgh @ 2024-07-31 09:35:47
@Brilliant11001 emmm,半年没写线段树了...
by zxr_zwgh @ 2024-07-31 09:36:49
@Brilliant11001 我对着之前的AC代码看看吧
by Brilliant11001 @ 2024-07-31 09:37:16
by zxr_zwgh @ 2024-07-31 09:40:21
@Brilliant11001 完了，今年提高感觉要挂...
#include<bits/stdc++.h>
using namespace std;
struct node{
int left,right;
int value,lazy=0;
}tree[4000005];
int a[1000005];
void build(int l,int r,int root){
tree[root].left=l,tree[root].right=r;
if(tree[root].left==tree[root].right){
tree[root].value=a[l];
return;
}
int mid=(tree[root].left+tree[root].right)/2;
build(l,mid,2*root);
build(mid+1,r,2*root+1);
tree[root].value=tree[root*2].value+tree[root*2+1].value;
}
void spread(int root){
if(tree[root].left==tree[root].right){
return;
}
int lazy=tree[root].lazy;
tree[root*2].lazy+=lazy;
tree[root*2+1].lazy+=lazy;
tree[root*2].value+=lazy*(tree[root*2].right-tree[root*2].left+1);
tree[root*2+1].value+=lazy*(tree[root*2+1].right-tree[root*2+1].left+1);
tree[root].lazy=0;
}
void update(int root,int l,int r,int v){
if(tree[root].left>=l&&tree[root].right<=r){
tree[root].lazy+=v;
tree[root].value+=(tree[root].right-tree[root].left+1);
return;
}
spread(root);
int mid=(tree[root].left+tree[root].right)/2;
if(l<=mid) update(root*2,l,r,v);
if(r>mid) update(root*2+1,l,r,v);
tree[root].value=tree[root*2].value+tree[root*2+1].value;
}
inline int query(int root,int l,int r){
if(tree[root].left>=l&&tree[root].right<=r){
return tree[root].value;
}
int ans=0;
spread(root);
int mid=(tree[root].left+tree[root].right)/2;
if(l<=mid) ans+=query(root*2,l,r);
if(r>mid) ans+=query(root*2+1,l,r);
return ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,n,1) ;
// for(int i=1;i<=n;i++) {
// cout<<query(1,i,i)<<" ";
// }
while(q--){
int op;
cin>>op;
if(op==1){
int l,r,v;
cin>>l>>r>>v;
update(1,l,r,v);
}else if(op==2){
int l,r;
cin>>l>>r;
cout<<query(1,l,r)<<"\n";
}
}
return 0;
}好像还有问题(悲