1923 字
10 分钟
BZOJ 1500 [NOI2005] 维护数列
2017-07-15
题解
Treap

【问题描述】#

564239476b322.gif 题目链接 BZOJ COGS

【输入格式】#

输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M表示要进行的操作数目。第 2 行包含 N 个数字，描述初始时的数列。以下 M 行，每行一条命令，格式参见问题描述中的表格。

【输出格式】#

对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。

【输入样例】#

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

【输出样例】#

-1
10
1
10

【样例说明】#

初始时，我们拥有数列 2 -6 3 5 1 -5 -3 6 3 执行操作 GET-SUM 5 4，表示求出数列中从第 5 个数开始连续 4 个数字之和，1+(-5)+(-3)+6 = -1：

2 -6 3 5 1 -5 -3 6 3

执行操作 MAX-SUM，表示要求求出当前数列中最大的一段和，应为 3+5+1+(-5)+(-3)+6+3 = 10：

2 -6 3 5 1 -5 -3 6 3

执行操作 INSERT 8 3 -5 7 2，即在数列中第 8 个数字后插入-5 7 2，

2 -6 3 5 1 -5 -3 6 -5 7 2 3

执行操作 DELETE 12 1，表示删除第 12 个数字，即最后一个：

2 -6 3 5 1 -5 -3 6 -5 7 2

执行操作 MAKE-SAME 3 3 2，表示从第 3 个数开始的 3 个数字，统一修改为 2：

2 -6 3 5 1 -5 -3 6 -5 7 2

改为

2 -6 2 2 2 -5 -3 6 -5 7 2

执行操作 REVERSE 3 6，表示取出数列中从第 3 个数开始的连续 6 个数：

2 -6 2 2 2 -5 -3 6 -5 7 2

如上所示的灰色部分 2 2 2 -5 -3 6，翻转后得到 6 -3 -5 2 2 2，并放回原来位置：

2 -6 6 -3 -5 2 2 2 -5 7 2

最后执行 GET-SUM 5 4 和 MAX-SUM，不难得到答案 1 和 10。

2 -6 6 -3 -5 2 2 2 -5 7 2

BZOJ 版

题解#

本题要求维护 动态连续最大连续和 和 区间和
所以要用 Max，和 Sum 来记录
类似线段树我们需要Pushdown和Pushup函数
此外对于Max 为了更新他的值，我们还需要维护两个变量 l，r 分别记录前缀最大和&后缀最大和

向上传递的#

  • 对于一个节点更新Max时要分一下几种情况讨论

    1. 它的左儿子的Max
    2. 它的右儿子的Max
    3. 它的左儿子的r加上本节点的权值v
    4. 它的右儿子的l加上本节点的权值v
    5. 它的左儿子的r加上本节点的权值v加上右儿子的l

    用一张图来表示是这样的

  • 我们还需要维护一个节点的 l 与上面相似 要分三种情况

    1. 它的左儿子的 l
    2. 它的左儿子的 sum 加上 本节点的权值v
    3. 它的左节点的 sum 加上 本节点的权值v 加上 他的右儿子的 l

    用另一张张图来表示是这样的

  • r与上面的相似

    1. 它的右儿子的 r
    2. 它的右儿子的 sum 加上 本节点的权值v
    3. 它的右节点的 sum 加上 本节点的权值v 加上 他的左儿子的 r

    不想画图了╭(╯^╰)╮

  • 然后是Sum 直接加起来就好了

向下传递的#

  • 首先是旋转标记

    1. 直接下传然后交换左右儿子即可
    2. 注意异或的用法

  • 然后是修改标记

    1. 首先你不能暴力修改 有一个点会超时，亲测

    2. 所以想线段树一样我们需要一个标记

    3. 下传时注意维护Max，sum，l，r 这些值

      对于Sum 直接乘就好

      对于Max,l,r 要分类讨论

      1. 如果改变的值为负数那这三个的值都未你改变成的值
      2. 否则这等于Sum

  • 对于插入
    直接新建一颗树插进去就可以了

最后一步 码代码 调程序#

能Pushdown() 就Pushdown()
能Pushup() 就Pushup()

fhq Treap 真好
如果打Splay 我会死的

另外需要注意如果子树为空的返回值

链接们#

fhq大佬 挖掘Treap的潜力 - fanhq666的日志
我的板子来源 非旋转Treap及可持久化[Merge,Split] Memphis’s Blog
附朋友的题解 [您有新的未分配科技点] 无旋treap：从单点到区间（例题 BZOJ1500&NOI2005 维护数列 ）
[您有新的未分配科技点]无旋treap：从好奇到入门（例题：bzoj3224 普通平衡树）

C++ Code#

/*
 * @Author: WildRage 
 * @Date: 2017-07-15 10:32:15 
 * @Last Modified by:   WildRage 
 * @Last Modified time: 2017-07-15 15:07:46 
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct Node
{
    int v, key, size, rev;
    int Max, l, r, sum, change;
    Node *ch[2];
    Node(int x)
    {
        v = x;
        key = rand();
        size = 1;
        rev = 0;
        change = -INF;
        Max = x;
        l = x;
        r = x;
        sum = x;
        ch[0] = ch[1] = NULL;
    }
#define size(_) ((_) ? (_)->size : (0))
#define sum(_) ((_) ? (_)->sum : (0))
#define l(_) ((_) ? (_)->l : (-INF))
#define r(_) ((_) ? (_)->r : (-INF))
#define Max(_) ((_) ? (_)->Max : (-INF))
#define change(_) ((_) ? (_)->change : (-INF))
    void Pushup()
    {
        size = 1 + size(ch[1]) + size(ch[0]);
        l = max(l(ch[0]), max(sum(ch[0]) + v, sum(ch[0]) + v + l(ch[1])));
        r = max(r(ch[1]), max(sum(ch[1]) + v, sum(ch[1]) + v + r(ch[0])));
        Max = max(Max(ch[0]), max(Max(ch[1]), max(r(ch[0]) + v, max(l(ch[1]) + v, max(r(ch[0]) + l(ch[1]) + v, v)))));
        sum = sum(ch[0]) + sum(ch[1]) + v;
    }
    void reverse()
    {
        if (!this)
            return;
        swap(ch[0], ch[1]);
        swap(l, r);
        rev ^= 1;
    }
    void Update()
    {
        if (!this)
            return;
        if (ch[1])
            ch[1]->change = change;
        if (ch[0])
            ch[0]->change = change;
        sum = size * change;
        v=change;
        l=r=Max=max(change,size*change);
        //change = -INF;
    }
    void Pushdown()
    {
        if (!this)
            return;
        if (rev)
        {
            ch[0]->reverse();
            ch[1]->reverse();
            rev = 0;
        }
        if (change != -INF)
        {
            ch[0]->Update();
            ch[1]->Update();
            change=-INF;
        }
    }
} * root;
typedef pair<Node *, Node *> DNode;
Node *Merge(Node *A, Node *B)
{
    if (!A)
        return B;
    if (!B)
        return A;
    if (A->key < B->key)
    {
        A->Pushdown();
        A->ch[1] = Merge(A->ch[1], B);
        A->Pushup();
        return A;
    }
    else
    {
        B->Pushdown();
        B->ch[0] = Merge(A, B->ch[0]);
        B->Pushup();
        return B;
    }
}
DNode Split(Node *rt, int k)
{
    if (!rt)
        return DNode(NULL, NULL);
    DNode o;
    rt->Pushdown();
    if (size(rt->ch[0]) >= k)
    {
        o = Split(rt->ch[0], k);
        rt->ch[0] = o.second;
        rt->Pushup();
        o.second = rt;
    }
    else
    {
        o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
        rt->ch[1] = o.first;
        rt->Pushup();
        o.first = rt;
    }
    return o;
}
Node *st[4000005];
Node *build(int m)
{
    //memset(st, 0, sizeof(st));
    Node *x, *last;
    int p = 0;
    int a;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &a);
        x = new Node(a);
        last = NULL;
        while (p && st[p]->key > x->key)
        {
            st[p]->Pushup();
            last = st[p];
            st[p--] = NULL;
        }
        if (p)
            st[p]->ch[1] = x;
        x->ch[0] = last;
        st[++p] = x;
    }
    while (p)
        st[p--]->Pushup();
    return st[1];
}
Node *kth(int k)
{
    DNode x = Split(root, k - 1);
    DNode y = Split(x.second, 1);
    Node *ans = y.first;
    root = Merge(Merge(x.first, ans), y.second);
    return ans;
}
int Rank(Node *rt, int x)
{
    if (!rt)
        return 0;
    return x <= rt->v ? Rank(rt->ch[0], x) : Rank(rt->ch[1], x) + size(rt->ch[0]) + 1;
}
void Insert(int x)
{
    int k = Rank(root, x);
    DNode y = Split(root, k);
    Node *n = new Node(x);
    root = Merge(Merge(y.first, n), y.second);
}
void remove(int x)
{
    int k = Rank(root, x);
    DNode a = Split(root, k);
    DNode b = Split(a.second, 1);
    root = Merge(a.first, b.second);
}
void flip(int i, int m)
{
    DNode x = Split(root, i - 1);
    DNode y = Split(x.second, m);
    y.first->reverse();
    root = Merge(x.first, Merge(y.first, y.second));
}
void dfs(Node *rt)
{
    if (rt)
    {
        rt->Pushdown();
        dfs(rt->ch[0]);
        printf("%d ", rt->v);
        dfs(rt->ch[1]);
    }
}
void Insert(int i, int tot)
{
    Node *x = build(tot);
    DNode y = Split(root, i);
    root = Merge(y.first, Merge(x, y.second));
}
void rmdfs(Node *rt)
{
    if (rt)
    {
        rmdfs(rt->ch[0]);
        rmdfs(rt->ch[1]);
    }
    delete rt;
}
void remove(int i, int tot)
{
    DNode x = Split(root, i - 1);
    DNode y = Split(x.second, tot);
    rmdfs(y.first);
    root = Merge(x.first, y.second);
}
void Update(int i, int tot, int c)
{
    DNode x = Split(root, i - 1);
    DNode y = Split(x.second, tot);
    y.first->change = c;
    y.first->Update();
    //Node *m = build(tot, c);
    //rmdfs(y.first);
    root = Merge(x.first, Merge(y.first, y.second));
}
int get_sum(int i, int tot)
{
    DNode x = Split(root, i - 1);
    DNode y = Split(x.second, tot);
    int ans = sum(y.first);
    root = Merge(x.first, Merge(y.first, y.second));
    return ans;
}
int Max_Sum()
{
    return Max(root);
}
int main()
{
    //freopen("seq2005.in", "r", stdin);
    //freopen("seq2005.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    root = build(n);
    //dfs(root);
    //printf("----------------------\n");
    int l, r, c;
    char s[16];
    for (int i = 1; i <= m; i++)
    {
        scanf("%s", s);
        switch (s[0])
        {
        case 'G':
            scanf("%d%d", &l, &r);
            printf("%d\n", get_sum(l, r));
            break;
        case 'D':
            scanf("%d%d", &l, &r);
            remove(l, r);
            break;
        case 'I':
            scanf("%d%d", &l, &r);
            Insert(l, r);
            break;
        case 'R':
            scanf("%d%d", &l, &r);
            flip(l, r);
            break;
        case 'M':
            if (s[2] == 'K')
            {
                scanf("%d%d%d", &l, &r, &c);
                Update(l, r, c);
            }
            else
            {
                printf("%d\n", Max_Sum());
            }
        }
        //printf("--------------------------------\n");
        //dfs(root);
        //printf("\n-----------DONE-----------------\n");
    }
    //while (1)
    ;
}
BZOJ 1500 [NOI2005] 维护数列
https://www.nekomio.com/posts/36/
作者
NekoMio
发布于
2017-07-15
许可协议
CC BY-NC-SA 4.0
BZOJ 2818 GCD
BZOJ 1875 [SDOI2009]HH去散步 矩阵乘
京ICP备19044785号-1
© 2024 NekoMio. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari