「NOI2005」维护数列-非旋Treap

维护一个数列，给定初始的 $n$ 个数字。

现有六种命令：

在第 $pos$ 个数后插入 $tot$ 个数
翻转从第 $pos$ 个数开始的 $tot$ 个数
删除从第 $pos$ 个数开始的 $tot$ 个数
查询从第 $pos$ 个数开始的 $tot$ 个数的和
设定从第 $pos$ 个数开始的 $tot$ 个数设定为 $c$
查询整个数列中和最大的连续子区间的和

链接

Luogu P2042

题解

这是一道经典的平衡树的题，被我用来练手非旋$Treap$。

因为我太弱了，所以写的很痛苦。

关于合并和分裂的主要思想参见非旋Treap学习笔记。

对于节点，要维护：

树的大小，树的权值和，树从左端点开始的最大连续和，树从右端点开始的最大连续和，和树的最大连续子区间和。

主要操作：

pushdown

往下 $push$ ，修改两个子节点并打上标记。

pushup

更新所有信息，维护三个 $\max$ 信息的方式有些特殊，但仔细想想应当能想到。

这里我被坑了。这个与线段树的区间最大查询有点不太一样，根节点也有代表的数，这个需要记住。

建树

构建笛卡尔树。详见非旋Treap学习笔记。

最大查询连续和

直接输出根节点维护的最大连续子区间的值即可。

插入

把即将插入的 $tot$ 个数按照上文的介绍方法建树。

把原来的数按照 $size$ 裂成两棵树，分别按顺序合起来就可以了。

接下来的操作都需要裂成三棵树，左边的有 $pos-1$ 个树，中间有 $tot$ 个数。

删除

直接删除中间子树，左右合并。因为内存不够（ $64MB$ ），需要垃圾回收。

求和

输出中间子树的和，再把三个子树顺次合并起来。

翻转

翻转中间子树并打标记，再把三个子树顺次合并起来。

设定

对中间子树完成设定并打标记，再将三个子树顺次合并起来。

还有一点就是垃圾回收。简略来说就是把删除的节点暴力的扔到一个栈里面，然后能用就用，不能有就再新开内存池。

其他也没有什么重要的。多 pushdown pushup几次，然后这些操作都是要注意边界，也就是 null 时候的条件的。pushup 的合并公式也需要好好斟酌。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 510000;

const int MAX = 2147483647;

int k,n;

struct node_t{
    int val,p;
    int lmax,rmax,maxn,sumn,tag;
    int size;
    bool rev,is_tag;
    node_t *son[2],**null;
    void pushdown(){
        if(this == *null) return;
        if(is_tag){
            son[0]->cover(tag),son[1]->cover(tag);
            is_tag = tag = 0;
        }
        if(rev) {
            son[0]->reverse(),son[1]->reverse();
            rev = 0;
        }
    }
    void pushup(){
        if(this == *null) return;
        if(son[0] == *null && son[1] == *null){
            size = 1;sumn = lmax = rmax = maxn = val;
            return;
        }
        size = son[0]->size + son[1]->size + 1;
        sumn = son[0]->sumn + son[1]->sumn + val;
        lmax = max(son[0]->lmax,son[0]->sumn + val + max(0,son[1]->lmax));
        rmax = max(son[1]->rmax,son[1]->sumn + val + max(0,son[0]->rmax));
        maxn = max(0,son[0]->rmax) + val + max(0,son[1]->lmax);
        maxn = max(maxn,max(son[0]->maxn,son[1]->maxn));
    }
    void cover(int v){
        if(this == *null) return;
        val = v;sumn = size * v;
        lmax = rmax = maxn = max(v,sumn);
        is_tag = 1;tag = v;
    }
    void reverse(){
        if(this == *null) return;
        swap(son[0],son[1]);
        swap(lmax,rmax);
        rev^=1;
    }
};


struct fhqtreap{
    node_t pool[MAXN],*tmp[MAXN],*stack[MAXN],*garbage[MAXN];
    node_t *root,*null;
    int cnt,tot;
    void newnode(node_t *&r,int val = 0){
        if(tot == 0) r = &pool[cnt++];
        else         r = garbage[--tot];//垃圾回收
        r->val = val;r->size = 1;
        r->lmax = r->rmax = r->maxn = r->sumn = val;
        r->son[0] = r->son[1] = null;
        r->is_tag = r->rev = 0;
        r->null = &null;
        r->p = rand();
    }
    fhqtreap(){
        tot = 0;cnt = 0;
        srand(time(NULL));
        newnode(null,-MAX);
        null->p = MAX;
        root = null;
        null -> sumn = null->size = 0;
    }
    void cycle(node_t *r){
        if(r == null) return;
        garbage[tot++] = r;
        cycle(r->son[0]);
        cycle(r->son[1]);
    }
    void read_tree(int n){
        for(int i = 1;i<=n;i++){
            int t;scanf("%d",&t);
            newnode(tmp[i],t);
        }
    }
    node_t *build(int n){
        read_tree(n);
        int top = 1;
        newnode(stack[0],-MAX);
        stack[0]->p = -MAX;
        for(int i = 1;i<=n;i++){
            int nowp = top - 1;
            node_t *r = tmp[i],*pre = null;
            while(stack[nowp]->p > r -> p){
                stack[nowp]->pushup();
                pre = stack[nowp];
                stack[nowp] = null;
                nowp--;
            }
            stack[nowp+1] = stack[nowp]->son[1] = r;
            stack[nowp+1]->son[0] = pre;
            top = nowp+2;
        }
        while(top) stack[--top]->pushup();
        return stack[0]->son[1];
    }
    void split(node_t *r,int lsize,node_t *&ls,node_t *&rs){
        if(r == null){
            ls = null;rs = null;return;
        }
        r->pushdown();
        if(r->son[0]->size + 1 <= lsize){
            ls = r;
            split(r->son[1],lsize-r->son[0]->size-1,ls->son[1],rs);
        }
        else{
            rs = r;
            split(r->son[0],lsize,ls,rs->son[0]);
        }
        ls->pushup();rs->pushup();
    }
    node_t *merge(node_t *ls,node_t *rs){
        if(ls == null) return rs;
        if(rs == null) return ls;
        if(ls->p < rs->p){
            ls->pushdown();
            ls->son[1] = merge(ls->son[1],rs);
            ls->pushup();
            return ls;
        }
        else{
            rs->pushdown();
            rs->son[0] = merge(ls,rs->son[0]);
            rs->pushup();
            return rs;
        }
    }
    void insert(int rank,int n){
        if(n == 0) return;
        node_t *ls,*rs,*newn,*ret;
        split(root,rank,ls,rs);
        newn = build(n);
        root = merge(merge(ls,newn),rs);
    }
    void split(int ls,int ms,node_t *&l,node_t *&m,node_t *&r){
        node_t *m1;
        split(root,ls,l,m1);
        split(m1,ms,m,r);
    }
    void erase(int lb,int ms){
        if(ms == 0) return;
        node_t *l,*m,*r,*ret;
        split(lb-1,ms,l,m,r);
        cycle(m);
        root = merge(l,r);
    }
    int get_sum(int lb,int ms){
        if(ms == 0) return 0;
        node_t *l,*m,*r;
        split(lb-1,ms,l,m,r);
        int ans = m->sumn;
        root = merge(l,merge(m,r));
        return ans;
    }
    int max_sum(){
        return root->maxn;
    }
    void reverse(int lb,int ms){
        if(ms == 0) return;
        node_t *l,*m,*r;
        split(lb-1,ms,l,m,r);
        m->reverse();       
        root = merge(l,merge(m,r));
    }
    void make_same(int lb,int ms,int c){
        if(ms == 0) return;
        node_t *l,*m,*r;
        split(lb-1,ms,l,m,r);
        m->cover(c);
        root = merge(l,merge(m,r));
    }
};

fhqtreap w;

void init(){
    scanf("%d %d",&n,&k);
    w.root = w.build(n);
}

void solve(){
    for(int i = 1;i<=k;i++){
        char op[50];int a,b,c;
        scanf("%s",op);
        if(op[0] == 'M'&&op[2] == 'X')
            printf("%d\n",w.max_sum());
        else{
            scanf("%d %d",&a,&b);
            if(op[0] == 'I')
                w.insert(a,b);
            else if(op[0] == 'D')
                w.erase(a,b);
            else if(op[0] == 'G'){
                printf("%d\n",w.get_sum(a,b));
            }
            else if(op[0] == 'M'){
                scanf("%d",&c);
                w.make_same(a,b,c);
            }
            else if(op[0] == 'R'){
                w.reverse(a,b);
            }
        }
    }
}

int main(){
    init();
    solve();
    return 0;
}

「NOI2005」维护数列-非旋Treap

链接

题解

代码

See Also

Comments