社区讨论
#3-#5 WA #6-#9 RE 求调
P13825【模板】线段树 1.5参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mhizj6s9
- 此快照首次捕获于
- 2025/11/03 18:16 4 个月前
- 此快照最后确认于
- 2025/11/03 18:16 4 个月前
做法是先对所有询问离线储存,然后离散化,套线段树。请各位佬帮忙看看。
CPP#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=1e5+5;
struct Ask{
int op,l,r,k;
}ask[N];
int n,m,cnt;
ll t[N<<2],lz[N<<2];
vector<int> X;
int find(int x){return lower_bound(X.begin(),X.end(),x)-X.begin()+1;}
int ls(int o){return o<<1;}
int rs(int o){return o<<1|1;}
void push_up(int o){
t[o]=t[ls(o)]+t[rs(o)];
}
void build(int s=1,int e=cnt,int o=1){
if (s==e){
ll L=X[s-1],R=(s==cnt?n:X[s]-1);
t[o]=(R-L+1)*(L+R)/2;
return;
}
int mid=(s+e)>>1;
build(s,mid,ls(o));
build(mid+1,e,rs(o));
push_up(o);
}
void f(int s,int e,int o,int x){
ll len=(s==e?1:X[e-1]-X[s-1]+1);
t[o]+=len*x;
lz[o]+=x;
}
void push_down(int s,int e,int o){
if (!lz[o])return;
int mid=(s+e)>>1;
f(s,mid,ls(o),lz[o]);
f(mid+1,e,rs(o),lz[o]);
lz[o]=0;
}
void update(int l,int r,int x,int s=1,int e=cnt,int o=1){
if (l<=s&&e<=r){
f(s,e,o,x);
return;
}
push_down(s,e,o);
int mid=(s+e)>>1;
if (mid>=l)update(l,r,x,s,mid,ls(o));
if (mid+1<=r)update(l,r,x,mid+1,e,rs(o));
push_up(o);
}
ll query(int l,int r,int s=1,int e=cnt,int o=1){
if (l<=s&&e<=r){
return t[o];
}
push_down(s,e,o);
int mid=(s+e)>>1;
ll res=0;
if (mid>=l)res+=query(l,r,s,mid,ls(o));
if (mid+1<=r)res+=query(l,r,mid+1,e,rs(o));
return res;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for (int i=1;i<=m;i++){
int op,l,r,k=0;
cin>>op>>l>>r;
if (op==1)cin>>k;
X.push_back(l);
X.push_back(r);
ask[i]={op,l,r,k};
}
sort(X.begin(),X.end());
X.erase(unique(X.begin(),X.end()),X.end());
cnt=X.size();
build();
for (int i=1;i<=m;i++){
int l=ask[i].l,r=ask[i].r,op=ask[i].op,x=ask[i].k;
int tl=find(l),tr=find(r);
if (op==1){
update(tl,tr,x);
}else if (op==2){
cout<<query(tl,tr)<<'\n';
}
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...