社区讨论
#1~9 RE #10AC 求调
P13825【模板】线段树 1.5参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mllc0jse
- 此快照首次捕获于
- 2026/02/14 04:20 5 天前
- 此快照最后确认于
- 2026/02/17 10:35 前天
CPP
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=1e6+10;
struct node{
ll l,r;
ll sum,add;
int ls,rs;
}t[N*4];
int tot=0;//节点个数
ll n,m;
void pushup(int k){
t[k].sum=0;
if(t[k].ls)t[k].sum+=t[t[k].ls].sum;
if(t[k].rs)t[k].sum+=t[t[k].rs].sum;
}
int new_node(int l,int r){
tot++,t[tot].l=l,t[tot].r=r;
t[tot].sum=t[tot].add=0;
t[tot].ls=t[tot].rs=0;
return tot;
}
void change(int k,ll v){
t[k].sum+=(t[k].r-t[k].l+1)*v;
t[k].add+=v;
}
void pushdown(int k){
if(t[k].add==0)return;
ll mid=(t[k].l+t[k].r)/2;
if(t[k].ls==0)t[k].ls=new_node(t[k].l,mid);
change(t[k].ls,t[k].add);
if(t[k].rs==0)t[k].rs=new_node(mid+1,t[k].r);
change(t[k].rs,t[k].add);
t[k].add=0;
}
void update(int &k,int x,int y,ll v){
if(k==0)k=new_node(1,n);
if(t[k].r<x||t[k].l>y)return;
if(t[k].l>=x&&t[k].r<=y){
change(k,v);
return;
}
pushdown(k);
ll mid=(t[k].l+t[k].r)/2;
if(x<=mid)update(t[k].ls,x,y,v);
if(y>mid)update(t[k].rs,x,y,v);
pushup(k);
}
ll query(int k,int x,int y){
if(k==0)return 0;
if(t[k].r<x||t[k].l>y)return 0;
if(t[k].l>=x&&t[k].r<=y)return t[k].sum;
pushdown(k);
ll mid=(t[k].l+t[k].r)/2;
ll res=0;
if(x<=mid)res=query(t[k].ls,x,y);
if(y>mid)res+=query(t[k].rs,x,y);
return res;
}
int main(){
cin>>n>>m;
int root=0;
while(m--){
int op,l,r;
ll k;
cin>>op>>l>>r;
if(op==1){
cin>>k;
update(root,l,r,k);
}else{
ll ys=(1LL*l+r)*(r-l+1)/2;
ll zj=query(root,l,r);
cout<<ys+zj<<"\n";
}
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...