求助:线段树1
  • 板块灌水区
  • 楼主XingnoYi
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/6 11:49
  • 上次更新2023/11/3 05:37:07
查看原帖
求助:线段树1
735797
XingnoYi楼主2023/8/6 11:49

全WA了

#include <iostream>
#define big long long
using namespace std;
big n,m;
big op,ll,rr,x;
big a[100007];
struct node{
	big l,r,sum,tag;
}t[100007*4];
void tags(big xq,big len,big i)
{
	t[i].tag += xq;
	t[i].sum += len*xq;
}
void pushdown(big l,big r,big i)
{
	big mid = (l+r)>>1;
	tags(t[i].tag,mid-l+1,i*2);
	tags(t[i].tag,r-mid,i*2+1);
	t[i].tag = 0;
}
void build(big l,big r,big i)
{
	t[i].l = l, t[i].r = r;
	t[i].tag = 0;
	if(l == r)
	{
		t[i].sum = a[l];
		return;
	}
	big mid = (l+r) >> 1;
	build(l,mid,i*2);
	build(mid+1,r,i*2+1);
	t[i].sum = t[i*2].sum+t[i*2+1].sum;
}
void update(big l,big r,big i)
{
	if(t[i].l >= l && t[i].r <= r)
	{
		tags(x,t[i].r-t[i].l+1,i);
		return;
	}
	if(!(t[i].l > r || t[i].r < l))
	{
		pushdown(l,r,i);
		update(l,r,i*2);
		update(l,r,i*2+1);
	    t[i].sum = t[i*2].sum+t[i*2+1].sum;
	}
	
}
big query(big l,big r,big i)
{
	if(t[i].l >= l && t[i].r <= r)
	{
		return t[i].sum;
	}
	if(!(t[i].l > r || t[i].r < l))
	{
        pushdown(l,r,i);
		return query(l,r,i*2)+query(l,r,i*2+1);
	}
	return 0;
}
int main()
{
	cin >> n >> m;
	for(big i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	build(1,n,1);
	for(big i = 1;i <= m;i++)
	{
		cin >> op;
		if(op == 1)
		{
			cin >> ll >> rr >> x;
			update(ll,rr,1);
		}
		else
		{
			cin >> ll >> rr;
			cout << query(ll,rr,1) << endl;
		}
	}
	return 0;
}
2023/8/6 11:49
加载中...