社区讨论

#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 条回复,欢迎继续交流。

正在加载回复...