违规紫衫
  • 板块P1001 A+B Problem
  • 楼主damuzhi
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/7 11:27
  • 上次更新2024/10/7 13:43:21
查看原帖
违规紫衫
1127424
damuzhi楼主2024/10/7 11:27

怎样优化?

#include<bits/stdc++.h>

using namespace std;

struct node{
	long long l,r;
	long long sum;
	long long lazy;	
}t[2000020 * 4];

long long a[2000020];

void update(long long i)
{
	t[i].sum = t[i << 1].sum + t[i << 1|1].sum;
}

void pushdown(long long i)
{
	t[i<<1].lazy += t[i].lazy;
	t[i<<1|1].lazy += t[i].lazy;
	
	t[i<<1].sum += (t[i<<1].r - t[i<<1].l+1) * t[i].lazy;
	t[i<<1|1].sum += (t[i<<1|1].r - t[i<<1|1].l+1) * t[i].lazy;
	
	t[i].lazy = 0;
	update(i);
}

void build_tree(long long i,long long l,long long r)
{
	t[i].l = l;
	t[i].r = r;
	if(l == r)
	{
		t[i].sum = a[l];
		return ;	
	}
	long long mid = (l + r) / 2;
	build_tree(i * 2,l,mid);
	build_tree(i * 2 + 1,mid + 1,r);
	update(i);
}

long long query(long long i,long long l,long long r)//在i这个节点内查询 l 到 r 的值
{
	if(r < t[i].l || l > t[i].r)
		return 0;
	if(l <= t[i].l && t[i].r <= r)
		return t[i].sum;
	
	pushdown(i);
	return query(i<<1,l,r) + query(i<<1|1,l,r);
}
int main()
{
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long n,m;
	n = 2,m = 1;
	cin >> a[1] >> a[2];
	build_tree(1,1,n);
	long long l,r;
	l = 1,r = 2;
	cout << query(1,l,r) << endl;
	return 0;
}
2024/10/7 11:27
加载中...