自动搬运

查看原文

来自洛谷，原作者为

	tjtdrxxz 要是把博士抬去寝室，会不会被人误会啊？干脆就这样子放着好了......？

搬运于2025-08-24 23:04:35，当前版本为作者最后更新于2024-10-02 10:17:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目要求我们写一个能加入，删除，去重，单点查询的数据结构，很容易能想到线段树。

但，数据范围让这道题变得有点坑，直接开 $10 ^ 9$ 的数组肯定是要寄的，所以我们可以考虑动态开点。

类似于主席树，我们每次查询一个点的时候，如果该点存在，就不管，不然我们就新建一个点。

加入操作很简单，直接把 $x$ 所在的点加上 $y$ 就好了，删除操作和加入操作一样，但注意是减去 $y$，去重操作其实也不难想，只用在根节点修改他的 lazy_tag，每次下传就好了，查询操作也很简单，单点查询板板。

因为我懒，所以我用的指针。

code：

# include "bits/stdc++.h"
# define int long long
using namespace std;
struct node
{
	int l; int r;
	node *ll, *rr;
	int sum, tag;
	node ()
	{
		l = 0, r = 0;
		ll = rr = NULL;
		tag = sum = 0;
	}
};
node *root;
node *push_up (node *ind)
{
	ind -> sum = 0;
	if (ind -> ll)
	{
		ind -> sum += ind -> ll -> sum;
	}
	if (ind -> rr)
	{
		ind -> sum += ind -> rr -> sum;
	}
	return ind;
}
node *push_down (node *ind)
{
	if (ind -> tag)
	{
		if (ind -> ll)
		{
			if (ind -> ll -> sum)
			{
				ind -> ll -> sum = ind -> ll -> r - ind -> ll -> l + 1;
				ind -> ll -> tag = ind -> tag;
			}
		}
		if (ind -> rr)
		{
			if (ind -> rr -> sum)
			{
				ind -> rr -> sum = ind -> rr -> r - ind -> rr -> l + 1;
				ind -> rr -> tag = ind -> tag;
			}
		}
		ind -> tag = 0;
	}
	return ind;
}
node *amend (int dis, node *ind, int l, int r, int x)
{
	if (!ind) ind = (new node ());
	ind -> l = l;
	ind -> r = r;
	if (l == r)
	{
		ind -> sum += x;
		if (ind -> sum < 0) ind -> sum = 0;
		return ind;
	}
	ind = push_down (ind);
	int m1 = l + r >> 1; if (m1 >= dis) ind -> ll = amend (dis, ind -> ll, l, m1, x);
	int m2 = m1 * 1 + 1; if (m2 <= dis) ind -> rr = amend (dis, ind -> rr, m2, r, x);
	push_up (ind);
	return ind;
}
int sum (int dis, node *ind, int l, int r)
{
	if (!ind) return 0;
	if (l == r)
	{
		return ind -> sum;
	}
	ind = push_down (ind);
	int m1 = l + r >> 1; if (m1 >= dis) return sum (dis, ind -> ll, l, m1);
	int m2 = m1 * 1 + 1; if (m2 <= dis) return sum (dis, ind -> rr, m2, r);
	return 0;
}
node *change (node *ind)
{
	ind -> tag = 1;
	ind -> sum = ind -> r - ind -> l + 1;
	return ind;
}
int m;
# define stdi stdin
# define stdo stdout
signed main ()
{
	setvbuf (stdi, (char*) calloc (1 << 20, sizeof (char)), _IOFBF, 1 << 20);
	setvbuf (stdo, (char*) calloc (1 << 20, sizeof (char)), _IOFBF, 1 << 20);
	scanf ("%lld", &m);
	do
	{
		int op, x, y;
		scanf ("%lld", &op);
		if (op == 1) scanf ("%lld %lld", &x, &y), root = amend (x, root, 1, 1000000000, y);
		if (op == 2) scanf ("%lld %lld", &x, &y), root = amend (x, root, 1, 1000000000, -y);
		if (op == 3) root = change (root);
		if (op == 4) scanf ("%lld", &x), printf ("%lld\n", sum (x, root, 1, 1000000000));
	} while (-- m);
}