社区讨论

这个快读是有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 条回复,欢迎继续交流。

正在加载回复...