题解：P11139 [APC001] D - Array Again

tjtdrxxz · 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);
}