社区讨论
关于规范写法
学术版参与者 11已保存回复 21
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 21 条
- 当前快照
- 1 份
- 快照标识符
- @mid73ccp
- 此快照首次捕获于
- 2025/11/24 21:41 3 个月前
- 此快照最后确认于
- 2025/11/24 22:31 3 个月前
写了个唐人线段树,没想到居然调出来了,不过应该还是很唐人
CPP#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100005];
template<typename T>
class seg_tree
{
private:
struct node
{
T data,lazy=0;
};
vector<node> tree;
int n=0;
const T* data_start;
void build_tree(int idx,int l,int r)
{
if(l==r)
{
tree[idx].data=data_start[l];
return;
}
int mid=l+(r-l)/2;
build_tree(idx*2+1,l,mid);
build_tree(idx*2+2,mid+1,r);
tree[idx].data=tree[idx*2+1].data+tree[idx*2+2].data;
return;
}
void push_down(int idx,int l,int mid,int r)
{
if(tree[idx].lazy)
{
tree[idx*2+1].data+=tree[idx].lazy*T(mid-l+1);
tree[idx*2+1].lazy+=tree[idx].lazy;
tree[idx*2+2].data+=tree[idx].lazy*T(r-mid);
tree[idx*2+2].lazy+=tree[idx].lazy;
tree[idx].lazy=0;
}
return;
}
T query_tree(int idx,int l,int r,int L,int R)
{
if(l>R||r<L) return T{};
if(L<=l&&r<=R) return tree[idx].data;
int mid=l+(r-l)/2;
push_down(idx,l,mid,r);
return query_tree(idx*2+1,l,mid,L,R)+query_tree(idx*2+2,mid
+1,r,L,R);
}
void update_tree(int idx,int l,int r,int L,int R,T k)
{
if(l>R||r<L) return;
if(L<=l&&r<=R)
{
tree[idx].data+=k*T(r-l+1),tree[idx].lazy+=k;
return;
}
int mid=l+(r-l)/2;
push_down(idx,l,mid,r);
update_tree(idx*2+1,l,mid,L,R,k);
update_tree(idx*2+2,mid+1,r,L,R,k);
tree[idx].data=tree[idx*2+1].data+tree[idx*2+2].data;
return;
}
public:
void build(const T* l,const T* r)
{
n=distance(l,r),data_start=l;
tree.resize(4*n);
build_tree(0,0,n-1);
}
T query(const T* L,const T* R)
{
int l=distance(data_start,L),r=distance(data_start,R)-1;
return query_tree(0,0,n-1,l,r);
}
void update(const T* L,const T* R,T k)
{
int l=distance(data_start,L),r=distance(data_start,R)-1;
update_tree(0,0,n-1,l,r,k);
return;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
seg_tree<long long> seg;
seg.build(a+1,a+n+1);
for(int i=1,cz,l,r;i<=m;i++)
{
cin>>cz>>l>>r;
if(cz==1)
{
long long k;
cin>>k;
seg.update(a+l,a+r+1,k);
}
else cout<<seg.query(a+l,a+r+1)<<endl;
}
return 0;
}
所以求问一下dalao,怎么样才能让它真的能在考场上写得出来,考场上肯定没那么多时间调边界问题
回复
共 21 条回复,欢迎继续交流。
正在加载回复...