路过dalao帮忙看看线段树为什么错了吧qwq
查看原帖
路过dalao帮忙看看线段树为什么错了吧qwq
519384
Link_Cut_Y楼主2021/12/12 11:04
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10;
struct Node
{
	int l, r, lazy, val;
}tr[N << 2];
int s[N], res;
int n, m;

void pushup(int u)
{
	tr[u].val = tr[u << 1].val + tr[u << 1 | 1].val;
}

void pushdown(int u)
{
	tr[u << 1].lazy += tr[u].lazy;
	tr[u << 1 | 1].lazy += tr[u].lazy;
	tr[u << 1].val += tr[u].lazy * (tr[u << 1].r - tr[u << 1].l + 1);
	tr[u << 1 | 1].val += tr[u].lazy * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
	tr[u].lazy = 0;
}

void build(int u, int l, int r)
{
	tr[u] = {l, r, 0};
	if (l == r)
	{
		tr[u].val = s[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int l, int r, int v)
{
	if (tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].lazy += v, tr[u].val += v * (tr[u].r - tr[u].l + 1);
		return;
	}
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if (tr[u].l <= mid) modify(u << 1, l, r, v);
	if (mid < tr[u].r) modify(u << 1 | 1, l, r, v);
	pushup(u);
}

int query(int u, int x)
{
	if (tr[u].l == x && tr[u].r == x)
		return tr[u].val;
	
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) >> 1;
	if (tr[u].l <= mid) query(u << 1, x);
	if (mid < tr[u].r) query(u << 1 | 1, x);
	pushup(u);
}

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i ++ )
		scanf("%d", &s[i]);
		
	build(1, 1, n);
	
	while (m -- )
	{
		int op, a, b, c;
		scanf("%d", &op);
		if (op == 1)
		{
			scanf("%d%d%d", &a, &b, &c);
			modify(1, a, b, c);
		}
		if (op == 2)
		{
			scanf("%d", &a);
			cout << query(1, a) << endl;
		}
	}
	
	return 0;
}
2021/12/12 11:04
加载中...