ljcnoi @ 2024-12-15 10:07:00
rt，10pts代码如下……
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long int a[100005],tree[400005],tag[400005];
long long int k;
int d,x,y;
void build(int l,int r,int x)
{
if(l<r)
{
int mid=(l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
}
if(l==r)
{
tree[x]=a[l];
}
else
{
tree[x]=tree[x*2]+tree[x*2+1];
}
}
void pushdown(int l,int r,int x)
{
if(tag[x])
{
int mid=(l+r)/2;
tag[x*2]+=tag[x];
tree[x*2]+=(mid-l+1)*tag[x];
tag[x*2+1]+=tag[x];
tree[x*2+1]+=(mid-l+1)*tag[x];
}
tree[x]=tree[x*2]+tree[x*2+1];
}
void update(int l,int r,long long int d,int ll,int rr,int x)
{
if(l<=ll&&r>=rr)
{
tag[x]+=d;
tree[x]+=(ll-rr+1)*d;
}
else
{
pushdown(ll,rr,x);
int mid=(ll+rr)/2;
if(l<=mid)
{
update(l,r,d,ll,mid,x*2);
}
if(r>mid)
{
update(l,r,d,mid+1,rr,x*2+1);
}
tree[x]=tree[x*2]+tree[x*2+1];
}
}
long long int query(int l,int r,int ll,int rr,int x)
{
if(l<=ll&&rr<=r)
{
return tree[x];
}
pushdown(ll,rr,x);
int mid=(ll+rr)/2;
long long int ans=0;
if(l<=mid)
{
ans+=query(l,r,ll,mid,x*2);
}
if(r>mid)
{
ans+=query(l,r,mid+1,rr,x*2+1);
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,n,1);
for(int i=1;i<=m;i++)
{
scanf("%d",&d);
if(d==2)
{
scanf("%d%d",&x,&y);
printf("%lld\n",query(x,y,1,n,1));
}
else
{
scanf("%d%d%lld",&x,&y,&k);
update(x,y,k,1,n,1);
}
}
return 0;
}by ICE__LX @ 2024-12-15 10:13:25
或许，您需要先把7级钩藏了再出来发贴。。
by ljcnoi @ 2024-12-15 10:16:00
@ICE__LX
非整活，真的从最开始就没学线段树，第一次写……
by Genius_Star @ 2024-12-15 10:17:17
今年 csp 7 级确实不需要线段树吧
by ICE__LX @ 2024-12-15 10:17:26
某人先学的线段树，后学的ST表和树状数组。。。
by ljcnoi @ 2024-12-15 10:17:41
改了一点，但还是离谱……
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long int a[100005],tree[400005],tag[400005];
long long int k;
int d,x,y;
void build(int l,int r,int x)
{
if(l<r)
{
int mid=(l+r)/2;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
tree[x]=tree[x*2]+tree[x*2+1];
}
else
{
tree[x]=a[l];
}
}
void pushdown(int l,int r,int x)
{
if(tag[x])
{
int mid=(l+r)/2;
tag[x*2]+=tag[x];
tree[x*2]+=(mid-l+1)*tag[x];
tag[x*2+1]+=tag[x];
tree[x*2+1]+=(r-mid)*tag[x];
}
tree[x]=tree[x*2]+tree[x*2+1];
}
void update(int l,int r,long long int d,int ll,int rr,int x)
{
if(l<=ll&&r>=rr)
{
tag[x]+=d;
tree[x]+=(ll-rr+1)*d;
}
else
{
pushdown(ll,rr,x);
int mid=(ll+rr)/2;
if(l<=mid)
{
update(l,r,d,ll,mid,x*2);
}
if(r>mid)
{
update(l,r,d,mid+1,rr,x*2+1);
}
tree[x]=tree[x*2]+tree[x*2+1];
}
}
long long int query(int l,int r,int ll,int rr,int x)
{
if(l<=ll&&rr<=r)
{
return tree[x];
}
pushdown(ll,rr,x);
int mid=(ll+rr)/2;
long long int ans=0;
if(l<=mid)
{
ans+=query(l,r,ll,mid,x*2);
}
if(r>mid)
{
ans+=query(l,r,mid+1,rr,x*2+1);
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build(1,n,1);
for(int i=1;i<=m;i++)
{
scanf("%d",&d);
if(d==2)
{
scanf("%d%d",&x,&y);
printf("%lld\n",query(x,y,1,n,1));
}
else
{
scanf("%d%d%lld",&x,&y,&k);
update(x,y,k,1,n,1);
}
}
return 0;
}by ICE__LX @ 2024-12-15 10:18:34
用链式建树吧@ljcnoi
by Polarisx @ 2024-12-15 10:19:01
错误点有点多，建议好好看一下自己的代码
by ljcnoi @ 2024-12-15 10:19:38
@Genius_Star
今年CSP会贪心+二分+DP就有300pts
by ICE__LX @ 2024-12-15 10:20:31
某人数学不好，T2公式没康懂。。。
by ljcnoi @ 2024-12-15 10:23:52
@Polarisx
大佬能帮我列出要注意的关键点吗？