NOI2005 维修数列
splay   发布于 2017-03-05   149人围观  1条评论
splay   发表于 2017-03-05   149人围观  1条评论

 [NOI2005]维修数列

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 13351  Solved: 4272
[Submit][Status][Discuss]

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。
第2行包含N个数字,描述初始时的数列。
以下M行,每行一条命令,格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个,输入文件大小不超过20MBytes。

Output

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

Sample Input

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
​

Sample Output

-1
10
1
10
​

HINT


 

Solution(题解)

splay操作集大成者,如果这道题能懂的话,基本就不用愁splay的题了吧……

不想说什么,做到心态爆炸才调出来……

好,那既然是基本操作题,那我们就来基本操作吧。。。

首先不得不说平衡树的性质,那就是关键字大的节点一定在关键字小的节点的右边→_→;反之同理。

然后来说区间操作。假设我们要对区间[L,R]进行操作,那么我们就把节点L-1 rotate到根,把节点R+1 rotate到L-1的右儿子,那么根的右儿子的左子树就是区间[L,R]。为什么呢?因为根的右儿子的左子树的所有节点都在L-1右边、R+1左边,所以满足根的有儿子的左子树的所有节点的关键字x都满足L-1 < x < R+1,自然就是所要的区间了。(当然这是针对序列而言,关键字为第几个数的情况下)

然后来说这道题的6个操作

首先来说MAKE-SAME和REVERSE操作,这两个操作就是更新找出所求区间对应的子树后的根节点,然后再打上lazy标记,然后随着rotate和find操作push_down下传标记就好。

但是因为要维护最大子段和(MAX-SEQUENCE操作),所以我们要维护maxleft,maxright和maxsequence三个变量,那么rotate的时候就要注意一个细节,就是在把左右儿子翻转后,还要交换maxleft和maxright的值。还有一个坑就是最大子段和最少要取一个点,所以可能是负值。

然后GET-SUM操作的话,就维护区间和就好了,不用多说。

INSERT操作。首先我们要在程序初始化的时候加入两个权值为-INF的节点,以便其他后续插入。因为要插入一个序列,所以如果一个一个插入的话,常数会非常大,我们不妨模仿线段树的做法,用二分递归的方法去插入,这样能减小树高,就能降低常数了(因为树高是影响splay常数大小的一个主要因素)。就像这样:

DELETE操作。直接找到指定区间,把指定区间对应子树的根节点设成null就行了。

对于每一次修改之后,要先把根的右儿子update,再把根update,以保证其正确性。

但是问题来了:4000000个值怎么开空间?

我们注意到,数列中最多有500000个数,所以我们就可以开一个数组rel(release数组)大小为500000,来回收删除时的节点空间(在程序中用id表示),因为我们的程序是用内存池写的。所以我们的新建节点和DELETE操作的具体实现就应该分别如下:


然后的话,update长成:

然后就差不多大功告成了,就是注意下在MAX-SEQUENCE操作之前需要先splay去push_down一下保证正确性。

Code(代码)

 

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 500005;
const int INF = 1e7;
struct splay_node{
    int w,sum,maxr,rev,maxl,maxs,siz,sc,sf,id;
    splay_node *pre,*ch[2];
    int get_wh(){
        return pre->ch[0] == this ? 0 : 1;
    }
    void update();
    void set_ch(int wh,splay_node *child);
    void push_down();
    void revv(){
        swap(ch[0],ch[1]);
        swap(maxl,maxr);
    }
    void ms(){
        sum = sc * siz;
        w = sc;
        maxl = maxr = maxs = max(sc,sc * siz); 
    }
}pool[maxn],*root,*l,*r,*null;
void splay_node::update(){
    sum = ch[1]->sum + ch[0]->sum + w;
    maxs = max(ch[0]->maxs,max(ch[1]->maxs,max(ch[0]->maxr,0) + max(ch[1]->maxl,0) + w));
    maxl = max(ch[0]->maxl,ch[0]->sum + w + max(ch[1]->maxl,0));
    maxr = max(ch[1]->maxr,max(ch[0]->maxr,0) + w + ch[1]->sum);
    siz = ch[0]->siz + ch[1]->siz + 1;
}
void splay_node::set_ch(int wh,splay_node *child){
    ch[wh] = child;
    if(child != null)child->pre = this;
    update();
}
void splay_node::push_down(){
    if(rev == 1){
        if(ch[0] != null){
            ch[0]->revv();
            ch[0]->rev ^= 1;
        }
        if(ch[1] != null){
            ch[1]->revv();
            ch[1]->rev ^= 1;
        }
        rev = 0;
    }
    if(sf){
        if(ch[0] != null){
            ch[0]->sc = sc;
            ch[0]->sf = 1;
            ch[0]->rev = 0;
            ch[0]->ms();
        }
        if(ch[1] != null){
            ch[1]->sc = sc;
            ch[1]->sf = 1;
            ch[1]->rev = 0;
            ch[1]->ms();
        }
        sf = sc = 0;
    }
}
int rel[maxn],tot = 0,top = 0;
void init(){
    null = pool;null->siz = 0;
    null->pre = null->ch[0] = null->ch[1] = null;
    null->sc = null->sf = null->rev = null->id = 0;
    null->w = null->sum = 0;
    null->maxs = null->maxl = null->maxr = -INF;
    root = null;
    for(int i = 0;i < maxn;++i)rel[i] = i;
}
inline splay_node *get_new(int value){
    tot += 1;
    top = rel[tot];
    rel[tot] = 0;
    splay_node *newone = pool + top;
    newone->siz = 1;
    newone->id = top;
    newone->pre = newone->ch[1] = newone->ch[0] = null;
    newone->w = newone->sum = value;
    newone->sc = newone->rev = newone->sf = 0;
    newone->maxs = newone->maxl = newone->maxr = value;
    return newone;
}
void rotate(splay_node *&now){
    splay_node *fa = now->pre;splay_node *grand = now->pre->pre;
    int wh = now->get_wh();
    fa->push_down();
    now->push_down();
    fa->set_ch(wh,now->ch[wh^1]);
    now->set_ch(wh^1,fa);
    now->pre = grand;
    if(grand != null)
        grand->ch[grand->ch[0] == fa ? 0 : 1] = now;
}
void splay(splay_node *now,splay_node *tar){
    for(;now->pre != tar;rotate(now))
        if(now->pre->pre != tar)now->get_wh() == now->pre->get_wh() ? rotate(now->pre) : rotate(now);
    if(tar == null)root = now;
}
int tmp[maxn];
char s[17];
int p,c,v,n,m;
splay_node *build(int L,int R){
    if(L > R)return null;
    int mid = (L + R) >> 1;
    splay_node *now = get_new(tmp[mid]);
    now->set_ch(0,build(L,mid - 1));
    now->set_ch(1,build(mid + 1,R));
    return now;
}
splay_node *find(splay_node *now,int k){
    now->push_down();
    if(now->ch[0]->siz + 1 == k)return now;
    else if(now->ch[0]->siz >= k)return find(now->ch[0],k);
    else return find(now->ch[1],k - now->ch[0]->siz - 1);
}
void insert(int pos,int cnt){
    for(int i = 1;i <= cnt;++i)tmp[i] = get_num();
    l = find(root,pos + 1);
    r = find(root,pos + 2);
    splay(l,null);splay(r,l);
    r->set_ch(0,build(1,cnt));
    r->update();l->update();
}
void dfs(splay_node *now){
    rel[tot] = now->id;
    tot -= 1;
    if(now->ch[0] != null)dfs(now->ch[0]);
    if(now->ch[1] != null)dfs(now->ch[1]);
}
void del(int pos,int cnt){
    l = find(root,pos);
    r = find(root,pos + cnt + 1);
    splay(l,null);splay(r,l);
    dfs(r->ch[0]);
    r->ch[0] = null;
    r->update();l->update();
}
void make_same(int pos,int cnt,int c){
    l = find(root,pos);
    r = find(root,pos + cnt + 1);
    splay(l,null);splay(r,l);
    r->ch[0]->sf = 1;
    r->ch[0]->sc = c;
    r->ch[0]->rev = 0;
    r->ch[0]->ms();
    r->update();l->update();
}
void rever(int pos,int cnt){
    l = find(root,pos);
    r = find(root,pos + cnt + 1);
    splay(l,null);splay(r,l);
    r->ch[0]->revv();
    r->ch[0]->rev ^= 1;
}
int get_sum(int pos,int cnt){
    l = find(root,pos);
    r = find(root,pos + cnt + 1);
    splay(l,null);splay(r,l);
    return r->ch[0]->sum;
}
int maxs(int pos,int cnt){
    l = find(root,pos);
    r = find(root,pos + cnt + 1);
    splay(l,null);
    splay(r,l);
    return r->ch[0]->maxs;
}
int main(){
    init();
    n = get_num();
    m = get_num();
    root = get_new(-INF);
    root->set_ch(1,get_new(-INF));
    insert(0,n);
    while(m--){
        scanf("%s",s);
        if(s[2] == 'X')printf("%d\n",maxs(1,tot-2));
        else{
            p = get_num();
            c = get_num();
            if(s[0] == 'I'){
                insert(p,c);
                continue;
            }
            if(s[0] == 'D'){
                del(p,c);
                continue;
            }
            if(s[0] == 'M'){
                v = get_num();
                make_same(p,c,v);
                continue;
            }
            if(s[0] == 'R'){
                rever(p,c);
                continue;
            }
            if(s[0] == 'G'){
                printf("%d\n",get_sum(p,c));
                continue;
            }
        }
    }
    return 0;
}
/*
INPUT I
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 1 11 -1 
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

OUTPUT I
1
10
-4
-1

INPUT II
39 19
261 -149 299 376 -516 452 402 591 -191 592 -155 612 915 -729 341 436 694 -636 541 131 -298 352 882 -697 219 181 -239 -156 972 807 496 457 -125 335 832 287 -449 675 401 
RESERVE 12 14
INSERT 27 10 -894 -960 715 942 340 -965 55 -839 -684 30 
MAX-SUM
INSERT 22 7 727 202 523 662 -740 -972 -638 
GET-SUM 3 14
MAX-SUM
MAKE-SAME 27 4 38
MAKE-SAME 25 2 -290
MAKE-SAME 33 4 -928
RESERVE 39 1
INSERT 9 9 -509 -374 -925 -470 -568 -563 -551 288 -281 
INSERT 7 4 -100 370 532 945 
MAKE-SAME 3 15 916
DELETE 25 14
INSERT 33 9 -32 -397 -136 -230 510 -106 471 -728 -951 
DELETE 27 10
GET-SUM 7 32
INSERT 6 1 -244 
GET-SUM 14 9

OUTPUT II
6939
2308
6703
6728
3186
*/
​

良心发福利,给你们多两组

上一篇: FFT模板 【UOJ】模板题库 多项式乘法

下一篇: Codeforce Round #398 div.2 C ----767C

立即登录,发表评论
没有帐号?立即注册
1 条评论