社区讨论
这个快读是有bug吗。。。
P3372【模板】线段树 1参与者 2已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mi7e1zcw
- 此快照首次捕获于
- 2025/11/20 20:09 4 个月前
- 此快照最后确认于
- 2025/11/20 20:09 4 个月前
突发奇想把线段树加上快读竟然WA了两个点...
CPP#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1000001;
ll n,m,ans,b,c,x,y,opt,a[MAXN*4];
struct ak
{
ll l;
ll r;
ll w;
ll f;
}tree[MAXN*4];
void read(ll &x)
{
int f=1;
x=0;
bool flag=true;
char s=getchar();
if(s==' ') flag=false;
while((s<'0'||s>'9')&&flag)
{
if(s=='-') f=-1;
s=getchar();
if(s==' ') flag=false;
}
while((s>='0'&&s<='9')&&flag)
{
x=x*10+s-'0';
s=getchar();
if(s==' ') flag=false;
}
x=x*f;
}
void write(ll x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void down(ll k)
{
tree[k*2].f+=tree[k].f;
tree[k*2+1].f+=tree[k].f;
tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
tree[k].f=0;
}
inline void build(ll l,ll r,ll k)
{
tree[k].l=l;tree[k].r=r;
if(l==r)
{
cin>>tree[k].w;
return;
}
int mid=(l+r)/2;
build(l,mid,k*2);
build(mid+1,r,k*2+1);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
inline void chan(ll k,ll x,ll y)
{
if(tree[k].l==tree[k].r)
{
tree[k].w+=y;
return;
}
int mid=(tree[k].l+tree[k].r)/2;
if(x<=mid) chan(k*2,x,y);
else chan(k*2+1,x,y);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
inline void chan1(ll k,ll a,ll b,ll x)
{
if(tree[k].l>=a&&tree[k].r<=b)
{
tree[k].w+=(tree[k].r-tree[k].l+1)*x;
tree[k].f+=x;
return;
}
if(tree[k].f) down(k);
int m=(tree[k].l+tree[k].r)/2;
if(a<=m) chan1(k*2,a,b,x);
if(b>m) chan1(k*2+1,a,b,x);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
void sum(ll k,ll x,ll y)
{
if(tree[k].l>=x&&tree[k].r<=y)
{
ans+=tree[k].w;
return;
}
if(tree[k].f) down(k);
int mid=(tree[k].l+tree[k].r)/2;
if(x<=mid) sum(k*2,x,y);
if(y>mid) sum(k*2+1,x,y);
}
int main()
{
read(n);read(m);
build(1,n,1);
for(int i=0;i<m;i++)
{
read(opt);
if(opt==1)
{
read(x);
read(y);
read(c);
chan1(1,x,y,c);
}
if(opt==2)
{
ans=0;
read(x);read(y);
sum(1,x,y);
write(ans);
cout<<endl;
}
}
return 0;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...