平衡树,AC但疑惑
查看原帖
平衡树,AC但疑惑
364848
Bodhi楼主2022/12/25 22:55

参考的代码

原先没在我的代码中加“org”这个变量(也就是参考的代码中的“val”),结果加上就能过,有大佬能解释一下吗

#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> rbt;

using ll = long long;
const int R = 1e5 + 10;
struct Node
{
	int l, r, size, tag;
	ll val, key, org;
} tree[R];
int tot, root;
mt19937 rd;
int crt(ll val)
{
	tree[++tot].size = 1;
	tree[tot].key = rd();
	tree[tot].val = tree[tot].org = val; //在这里用到
	return tot;
}
void pushdown(int k)
{
	if (tree[k].tag != LLONG_MIN)
	{
		tree[k].val += ll(tree[k].tag) * ll(tree[k].size);
		tree[k].org += tree[k].tag; //这里用到
		if (tree[k].l)
			tree[tree[k].l].tag += tree[k].tag;
		if (tree[k].r)
			tree[tree[k].r].tag += tree[k].tag;
		tree[k].tag = 0;
	}
}
void pushup(int k)
{
	pushdown(tree[k].l);
	pushdown(tree[k].r);
	tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + 1;
	tree[k].val = tree[tree[k].l].val + tree[tree[k].r].val + tree[k].org; //这里用到,也就以上这3处了
}
void split(int k, int sz, int &x, int &y)
{
	if (k == 0)
	{
		x = y = 0;
		return;
	}
	pushdown(k);
	if (tree[tree[k].l].size + 1 <= sz)
	{
		x = k;
		split(tree[k].r, sz - (tree[tree[k].l].size + 1), tree[k].r, y);
	}
	else
	{
		y = k;
		split(tree[k].l, sz, x, tree[k].l);
	}
	pushup(k);
}
int merge(int x, int y)
{
	if (x == 0 || y == 0)
		return x + y;
	if (tree[x].key < tree[y].key)
	{
		pushdown(x);
		tree[x].r = merge(tree[x].r, y);
		pushup(x);
		return x;
	}
	else
	{
		pushdown(y);
		tree[y].l = merge(x, tree[y].l);
		pushup(y);
		return y;
	}
}
void update(int l, int r, int val)
{
	int x, y, z;
	split(root, l - 1, x, y);
	split(y, r - l + 1, y, z);
	tree[y].tag += val;
	root = merge(merge(x, y), z);
}
ll query(int l, int r)
{
	int x, y, z;
	split(root, l - 1, x, y);
	split(y, r - l + 1, y, z);
	pushdown(y);
	ll res = tree[y].val;
	root = merge(merge(x, y), z);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, x, y, k;
	char t;
	cin >> n >> m;
	int j;
	for (j = 1; j <= n; ++j)
	{
		cin >> x;
		root = merge(root, crt(x));
	}
	for (j = 1; j <= m; ++j)
	{
		cin >> t;
		if (t == '1')
		{
			cin >> x >> y >> k;
			update(x, y, k);
		}
		else
		{
			cin >> x >> y;
			cout << query(x, y) << '\n';
		}
	}
	return 0;
}
2022/12/25 22:55
加载中...