liuchenyu2022 @ 2023-03-04 16:03:07
这份代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
long long x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m;
struct node{
int le,ri;
unsigned long long sum;
unsigned long long zy;
}tree[4*1000001];
unsigned long long d[1000001];
void push_up(int p)
{
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
void build(int rt,int le,int ri)//构建线段树
{
tree[rt].le=le;
tree[rt].ri=ri;
tree[rt].zy=0;
if(le==ri)
{
tree[rt].sum=d[le];
return ;
}
int mid=(le+ri)>>1;
build(rt<<1,le,mid);
build((rt<<1)+1,mid+1,ri);
push_up(rt);
return ;
}
void lazy(int rt,unsigned long long k)
{
tree[rt].zy+=k;
tree[rt].sum += k*(tree[rt].ri-tree[rt].le+1);
}
void push_down(int rt)
{
lazy(rt<<1,tree[rt].zy);
lazy(rt<<1|1,tree[rt].zy);
tree[rt].zy=0;
}
void update(int rt,int nl,int nr,unsigned long long k)//单点修改
{
if(nl<=tree[rt].le&&nr>=tree[rt].ri)
{
lazy(rt,k);
return ;
}
push_down(rt);
unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
if(nl<=mid)
update(rt<<1,nl,nr,k);
if(nr>mid)
update((rt<<1)+1,nl,nr,k);
push_up(rt);
return ;
}
unsigned long long query1(int rt,int le,int ri)//查询[le...ri]的和
{
// 如果
if(le<=tree[rt].le&&tree[rt].ri<=ri)
return tree[rt].sum;
push_down(rt);
unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
unsigned long long Sum=0;
if(le<=mid)
Sum+=query1(rt<<1,le,ri);
if(ri>mid)
Sum+=query1((rt<<1)+1,le,ri);
return Sum;
}
long long query2(int rt,int le,int ri)//查询[le...ri]的和
{
if(tree[rt].le==le&&tree[rt].ri==ri)
return tree[rt].sum;
push_down(rt);
long long mid=(tree[rt].le+tree[le].ri)/2;
if(ri<=mid)
return query2(rt<<1,le,ri);
else if(le>mid)
return query2((rt<<1)+1,le,ri);
else
return query2(rt<<1,le,mid)+query2((rt>>1)+1,mid+1,ri);
}
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)
d[i]=read();
build(1,1,n);
for(int i=1;i<=m;i++)
{
int tmp=read();
if(tmp==1){
int le =read();
int ri= read();
// int val =read();
update(1,le,ri,read());
}
else
{
int le =read();
int ri= read();
// cout<<query1(1,le,ri)<<"\n";
printf("%lld\n",query1(1,le,ri));
}
}
return 0;
}
是对的\ \ 这份代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
inline unsigned long long read()
{
long long x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m;
struct node{
int le,ri;
unsigned long long sum;
unsigned long long zy;
}tree[4*1000001];
unsigned long long d[1000001];
void push_up(int p)
{
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
void build(int rt,int le,int ri)//构建线段树
{
tree[rt].le=le;
tree[rt].ri=ri;
tree[rt].zy=0;
if(le==ri)
{
tree[rt].sum=d[le];
return ;
}
int mid=(le+ri)>>1;
build(rt<<1,le,mid);
build((rt<<1)+1,mid+1,ri);
push_up(rt);
return ;
}
void lazy(int rt,unsigned long long k)
{
tree[rt].zy+=k;
tree[rt].sum += k*(tree[rt].ri-tree[rt].le+1);
}
void push_down(int rt)
{
lazy(rt<<1,tree[rt].zy);
lazy(rt<<1|1,tree[rt].zy);
tree[rt].zy=0;
}
void update(int rt,int nl,int nr,unsigned long long k)//单点修改
{
if(nl<=tree[rt].le&&nr>=tree[rt].ri)
{
lazy(rt,k);
return ;
}
push_down(rt);
unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
if(nl<=mid)
update(rt<<1,nl,nr,k);
if(nr>mid)
update((rt<<1)+1,nl,nr,k);
push_up(rt);
return ;
}
unsigned long long query1(int rt,int le,int ri)//查询[le...ri]的和
{
// 如果
if(le<=tree[rt].le&&tree[rt].ri<=ri)
return tree[rt].sum;
push_down(rt);
unsigned long long mid=(tree[rt].le+tree[rt].ri)/2;
unsigned long long Sum=0;
if(le<=mid)
Sum+=query1(rt<<1,le,ri);
if(ri>mid)
Sum+=query1((rt<<1)+1,le,ri);
return Sum;
}
long long query2(int rt,int le,int ri)//查询[le...ri]的和
{
if(tree[rt].le==le&&tree[rt].ri==ri)
return tree[rt].sum;
push_down(rt);
long long mid=(tree[rt].le+tree[le].ri)/2;
if(ri<=mid)
return query2(rt<<1,le,ri);
else if(le>mid)
return query2((rt<<1)+1,le,ri);
else
return query2(rt<<1,le,mid)+query2((rt>>1)+1,mid+1,ri);
}
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)
d[i]=read();
build(1,1,n);
for(int i=1;i<=m;i++)
{
int tmp=read();
if(tmp==1){
update(1,read(),read(),read());
}
else
{
int le =read();
int ri= read();
// cout<<query1(1,le,ri)<<"\n";
printf("%lld\n",query1(1,le,ri));
}
}
return 0;
}
是错的
by liuchenyu2022 @ 2023-03-04 16:15:38
咋回事啊?
by pjykk @ 2023-03-04 16:18:00
update(1,read(),read(),read());
不要这么写。是UB。
by liuchenyu2022 @ 2023-07-04 14:26:26
谢谢