icontofig | 发布于 2017-01-08 09:23:48 | 阅读量 360 | splay 线段树
发布于 2017-01-08 09:23:48 | splay 线段树

题目描述

小Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一。经过仔细观察,小Q发现统计一张报表实际上是维护一个可能为负数的整数数列,并且进行一些查询操作。在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作: INSERT i k 在原数列的第i个元素后面添加一个新元素k; 如果原数列的第i个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子) MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值 MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值(绝对值) 例如一开始的序列为 5 3 1 执行操作INSERT 2 9将得到: 5 3 9 1 此时MIN_GAP为2,MIN_SORT_GAP为2。 再执行操作INSERT 2 6将得到: 5 3 9 6 1 注意这个时候原序列的第2个元素后面已经添加了一个9,此时添加的6应加在9的后面。这个时候MIN_GAP为2,MIN_SORT_GAP为1。于是小Q写了一个程序,使得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?

输入格式

第一行包含两个整数N,M,分别表示原数列的长度以及操作的次数。第二行为N个整数,为初始序列。接下来的M行每行一个操作,即“INSERT i k”,“MIN_GAP”,“MIN_SORT_GAP”中的一种(无多余空格或者空行)。

输出格式

对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。

样例输入

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

样例输出

2
2
1

数据范围及提示

N , M ≤500000 对于所有的数据,序列内的整数不超过5*108


题解

于是这道题有点坑啊。
初学splay,拿几道题目练练手,结果没想到刚开始推荐的这个就这么坑。
观察题目中的信息,我们发现,其实是可以用2个splay做的,一个splay维护MIN_GAP,另一个维护MIN_SORT_GAP,每次添加的时候只要注意:
1.由于满足单调性MIN_SORT_GAP只需要先求出排在当前要添加的数的前面和后面的两个数,用这两个数和当前要添加的数的差值的绝对值更新MIN_SORT_GAP,然后添加这两个差值就好了。
2.MIN_GAP操作比较麻烦,需要删除当前添加位置之前和之后两个数的差值的绝对值,然后添加当前添加的数和刚才那两个数的差值的绝对值进去。但是切记不可更新MIN_GAP,因为MIN_GAP不单调。
但是这样的结果却是……

(自测的时候最大的数据点跑了10s+)

众所周知,splay的常数是巨大的,所以我们要重新考虑一下
MIN_SORT_GAP满足单调性,做法正确,这么说,MIN_GAP应该还有另外的求法。。。
我们注意到,如果我们把每个位置上加入的所有数看成一个组的话,先不考虑组间MIN_GAP,那么每个组内的MIN_GAP都是单调的!这样的话我们只需要用一个变量维护组内MIN_GAP最小就行了
至于每次插入还有组间的MIN_GAP问题,这个就好解决了,每次只修改一个数的话……
没错!线段树点修改!这样我们的时间复杂度就降到合适的范围了。查询的话,比较组内MIN_GAP变量和线段树的顶点处记录的min值就行了。

题解完……

代码(有点长……)

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,p1,p2;
int msg,pos,value,mg;
const int INF = 2147483647; 
const int maxn = 500005;
int a[maxn<<2],b[maxn<<2];
struct splay_node{
    int value,siz,cnt;
    splay_node *pre,*ch[2];
    void update(){
        siz = ch[0]->siz + ch[1]->siz + cnt;
    }
    int get_wh(){
        return pre->ch[0] == this ? 0 : 1;
    }
    void set_ch(int wh,splay_node *child);
}pool[maxn<<2],*root,*null;
int top = 0;
splay_node *get_new(int value){
    splay_node *now = pool + ++top;
    now->siz = now->cnt = 1;
    now->value = value;
    now->pre = now->ch[1] = now->ch[0] = null;
    return now;
}
void splay_node::set_ch(int wh,splay_node *child){
    ch[wh] = child;
    if(child != null)
        child->pre = this;
    update();
    return;
}
void rotate(splay_node *&now){
    splay_node *oldf = now->pre;
    splay_node *grand = now->pre->pre;
    int wh = now->get_wh();
    oldf->set_ch(wh,now->ch[wh^1]);
    now->set_ch(wh^1,oldf);
    now->pre = grand;
    if(grand != null)
        grand->ch[oldf == grand->ch[0] ? 0 : 1] = now;
    return;
}
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;
}
void insert(int value){
    splay_node *newone = get_new(value);
    splay_node *last = null,*now = root;
    while(now != null){
        last = now;
        if(newone->value == now->value){
            now->cnt += 1;
            now->siz += 1;
            splay(now,null);
            return;
        }
        if(now->value < newone->value)
            now = now->ch[1];
        else now = now->ch[0];
    }
    if(last == null)
        root = newone;
    else{
        if(newone->value < last->value)
            last->set_ch(0,newone);
        else
            last->set_ch(1,newone);
        splay(newone,null);
    }
    return;
}
int pre(int value){
    splay_node *now = root;
    int ans = -INF;
    while(now != null){
        if(now->value > value)
            now = now->ch[0];
        else if(now->value == value)
            return now->value;
        else if(now->value < value){
            ans = max(ans,now->value);
            now = now->ch[1];
        }
    }
    return ans;
}
int nxt(int value){
    splay_node *now = root;
    int ans = INF;
    while(now != null){
        if(now->value < value)
            now = now->ch[1];
        else if(now->value == value)
            return now->value;
        else if(now->value > value){
            ans = min(ans,now->value);
            now = now->ch[0];
        }
    }
    return ans;
}
void init(){
    null = pool;
    null->pre = null->ch[1] = null->ch[0] = null;
    null->cnt = null->siz = 0;
    null->value = 0;
    root = null;
}
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;
}
struct seg_tree{
    int l,r,value,sec_value;
}tr[maxn<<3];
void push_up(int now){
    if(tr[now<<1].value <= tr[now<<1|1].value){
        tr[now].value = tr[now<<1].value;
        tr[now].sec_value = min(tr[now<<1].sec_value,tr[now<<1|1].value);
    }
    else{
        tr[now].value = tr[now<<1|1].value;
        tr[now].sec_value = min(tr[now<<1].value,tr[now<<1|1].sec_value);
    }
    return;
}
void build(int now,int l,int r){
    tr[now].l = l;
    tr[now].r = r;
    tr[now].value = tr[now].sec_value = INF;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    push_up(now);
}
void upd(int now,int pos,int k){
    if(tr[now].l == tr[now].r){
        tr[now].value = k;
        return;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)upd(now<<1,pos,k);
    else upd(now<<1|1,pos,k);
    push_up(now);
}
char s[20];
int main(){
    init();
    n = get_num();
    m = get_num();
    build(1,1,m+n);
    mg = INF;
    msg = INF;
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
        b[i] = a[i];
        if(i == 1){
            insert(a[i]);
            continue;
        }
        p1 = pre(a[i]);
        p2 = nxt(a[i]);
        insert(a[i]);
        if(p1 != -INF)
            msg = min(msg,a[i] - p1);
        if(p2 != INF)
            msg = min(msg,p2 - a[i]);
        upd(1,i-1,abs(a[i] - b[i-1]));
    }
    for(int i = 1;i <= m;++i){
        scanf("%s",s);
        if(s[0] == 'I'){
            pos = get_num();
            value = get_num();
            p1 = pre(value);
            p2 = nxt(value);
            insert(value);
            if(p1 != -INF)
                msg = min(msg,value - p1);
            if(p2 != INF)
                msg = min(msg,p2 - value);
            if(pos == n){
                mg = min(mg,abs(value - b[pos]));
                b[pos] = value;
                continue;
            }
            mg = min(mg,abs(value - b[pos]));
            upd(1,pos,abs(a[pos+1] - value));
            b[pos] = value;
        }
        else if(s[4] == 'G')
            printf("%d\n",min(mg,tr[1].value));
        else
            printf("%d\n",msg);
    }
    return 0;
}
​


 


内容更新于: 2017-01-08 09:25:28
链接地址: http://blog.leanote.com/post/icontofig/%E3%80%90%E3%80%91

上一篇: 【BZOJ3507【CQOI】通配符匹配DP+Hash

下一篇: splay核心代码(指针)

360 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航