题解 P2042 【[NOI2005]维护数列】

Ofnoname · 2019-10-05 22:38:09 · 题解

FHQ treap 详细做法

尽管题解巨多，FHQ treap却并没有多少人用，所以还是可以写题解的。

在阅读本文之前，你应该学过FHQ treap，会打split和merge函数

#define i0 a[i].L//左子树
#define i1 a[i].R//右子树
struct Node
{
    int L, R, se, z, f0, f, size;
    int sum, max, max0, max1;
}a[MAX];

void split(int i, int &x, int &y, int k)
{
    if (!i)
    {
        x = y = 0;
        return;
    }
    pushtag(i);
    if (a[i0].size < k)
        x = i, split(i1, i1, y, k-a[i0].size-1);
    else
        y = i, split(i0, x, i0, k);
    update(i);
}

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (a[x].se < a[y].se)
    {
        pushtag(x);
        a[x].R = merge(a[x].R, y);
        return update(x), x;
    }
    pushtag(y);
    a[y].L = merge(x, a[y].L);
    return update(y), y;
}

1. 平衡树进行区间操作的本质。

在做平衡树模板时，只涉及到了“插入数”和“删除数”，并没有具体的序列（除非你用数组做）。

而进行区间操作时，区间的下标满足BST性质，整棵树的中序遍历直接构成这个序列，序列的权值存在点里，而节点本身的编号什么也不代表。

所以对区间[pos, pos+len-1]进行操作时，只需要split两次，将treap裂为三段，并对中间一段进行操作，然后再merge即可。

split(root, x, y, pos);//将整棵树的前pos给x
split(y, y, z, len-1)//将后半段的前len-1给y，剩下的是z
//对y进行操作
root = merge(merge(x, y), z)//将三段合并

2. 内存问题

本题操作数为4e6，如果开4e6的数组，由于每个节点信息很多，会MLE。

但是序列里最多只有5e5个数，我们可以在删除时将删掉的节点存储下来（放进栈里），再创建新节点时，如果栈中有数就再用一次这个数，可以省下内存。注意先将节点清空。

int top, S[MAX];
int New(int z)
{
    int id = top ? S[top--] : ++nc;//取栈中节点
    memset(a+id, 0, sizeof(Node));
    a[id].sum = a[id].z = a[id].max = z;
    a[id].max0 = a[id].max1 = max(0, z);//max可以参见后文
    a[id].size = 1, a[id].se = rand();
    return id;

}

3. 插入数

首先，无论是初始化还是中途的INSERT都是一次插入多个数，我们知道插入一个数是需要split一次，merge一次的，如果一个一个插入将会很浪费。

我们可以在pos处直接断开，然后在前一半添加一个包含所有待添加数的新treap，再把两段合并。这样就只用split一次。

如何用数列构造新treap呢？可以折半递归，分别申请新节点，再往上合并，这merge只用执行log级别的次数。

int add(int L, int R)
{
    if (L != R)
    {
        int mid = (L + R) >> 1;
        return merge(add(L,mid), add(mid+1,R));
    }return New(t[L]);
}

for (int i = 1; i <= N; i++)//Init
    scanf("%d", &t[i]);
root = merge(root, add(1, N));

if (op[2] == 'S')//Insert
{
    split(root, x, y, pos);
    for (int i = 1; i <= len; i++)
        scanf("%d", &t[i]);
    root = merge(merge(x, add(1, len)), y);
}

4. 删除数

很简单，按照1里的代码将treap拆解为3段，将中间一段删除即可。

由于要将删掉的数不可能再用到，要立即存入回收站以供使用，没有必要使用懒标记，直接递归删除即可。

void rmv(int i)
{
    S[++top] = i;
    if (i0) rmv(i0);
    if (i1) rmv(i1);
}
if (op[2] == 'L')//Delete
{
    split(root, x, y, pos-1), split(y, y, z, len);
    rmv(y)， root = merge(x, z);
}

5. 区间推平

把要推平的区间拿出来，取第一个点打上懒标记。懒标记与线段树的相同（即要先更新自己，再打标记）。

void cover(int i, int c)
{
    a[i].z =  c;//更新自己的权值
    a[i].sum = a[i].size * c;//更新区间和
    a[i].max0 = a[i].max1 = max(0, a[i].sum);
    a[i].max = max(c, a[i].sum);//max可参见后文
    a[i].f0 = 1;//懒标记
}
if (op[2] == 'K')//Make_Same
{
    scanf("%d", &c);
    split(root, x, y, pos-1), split(y, y, z, len);
    cover(y, c);
    root = merge(merge(x, y), z);
}

6. 翻转

同上，要打懒标记。但是懒标记可以写作f ^= 1。这是因为翻转两次就相当于没有翻转，所以f = 1时在打标记就是0。

void reverse(int i)
{
    swap(i0, i1), swap(a[i].max0, a[i].max1);//max参见后文
    a[i].f ^= 1;
}

if (op[2] == 'V')//Reverse
{
    split(root, x, y, pos-1), split(y, y, z, len);
    reverse(y);
    root = merge(merge(x, y), z);
}

7. 懒标记下推

推平和翻转的标记都要推，先后顺序没关系。清楚标记，并将左右节点调用reverse/cover即可，左右子树cover的值显然应该是本节点的权值。

void pushtag(int i)
{
    if (!i) return;
    if (a[i].f)
    {
        if (i0) reverse(i0);
        if (i1) reverse(i1);
        a[i].f = 0;
    }
    if (a[i].f0)
    {
        if (i0) cover(i0, a[i].z);
        if (i1) cover(i1, a[i].z);
        a[i].f0 = 0;
    }
}

8. 查询区间和

中等简单。a[i].sum代表自己和自己子树构成区间的权值总和。

每个点在创建时的sum显然应赋值为自己的权值。（参见前文New()）

而update时显然有a[i].sum = a[i0].sum + a[i1].sum + a[i].z。（参见后文）

将给定区间拆解输出即可。

if (op[2] == 'T')//GET_SUM
{
    split(root, x, y, pos-1), split(y, y, z, len);
    printf("%d\n", a[y].sum);
    root = merge(merge(x, y), z);
}

9. 查询最大子段和

最难最麻烦。本题的子段和至少选一个数。

维护每个点及其子树构成区间的最大前缀和max0，最大后缀和max1和最大子段和max。

显然每个点在创建时这些都应赋值为自己的权值（参见前文New()）

update时，一段[L,R]最大前缀和可以有“终点在mid左端（a[i0].max0）”和“终点在mid右（a[i0].sum + a[i].z + a[i1].max0）`”两种情况，取最大值即可。

最小后缀和同理，有a[i].max1 = max(a[i1].max1, a[i1].sum + a[i].z + a[i0].max1

而最大子段和max就是左端和最大后缀和与右端的最大前缀和之和。或者不经过i点，取两边的max值

a[i].max = a[i0].max1 + a[i1].max0 + a[i].z;
a[i].max = max(a[i].max, max(a[i0].max, a[i1].max));

翻转区间时，显然后缀和，前缀和反了，所以要swap(a[i].max0, a[i].max1)。

需要注意的是，由于不能有空段，所以max赋值时不能与0取最大，但是当拼接a[i].max时，我们发现i自己的权值是必选的，即使max0，max1为空，整个序列也是有一个i点的。因此可以让max0，max1计算时与0取最大（即什么都不选）。

有了8，9两点，update函数不难写出：

void update(int i)
{
    if (!i) return;
    a[i].size = a[i0].size + a[i1].size + 1;
    a[i].sum = a[i0].sum + a[i1].sum + a[i].z;
    a[i].max0 = max(max(a[i0].max0, a[i0].sum + a[i].z + a[i1].max0), 0);
    a[i].max1 = max(max(a[i1].max1, a[i1].sum + a[i].z + a[i0].max1), 0);
    a[i].max = max(a[i0].max1 + a[i1].max0, 0) + a[i].z;
    if (i0) a[i].max = max(a[i].max, a[i0].max);
    if (i1) a[i].max = max(a[i].max, a[i1].max);
}

else printf("%d\n", a[root].max);//MAX-SUM

至此问题已经全部解决。

谢谢观看，完结撒花。