洛谷 P1110 [ZJOI2007]报表统计 题解【splay】【set】

作者: wjyyy 分类: set,splay,解题报告 发布时间: 2018-06-17 18:20

点击量:18

 

   一道splay的正常题,不过因为考试的时候一句话读错了于是开了2 splay +1 set 棵平衡树。。。事实上为了卡过这道题用1 splay + 1 set 是可以过洛谷神鸡的。

 

题目描述

小Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一。

 

经过仔细观察,小Q发现统计一张报表实际上是维护一个非负整数数列,并且进行一些查询操作。

 

在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作:

 

  • INSERT i k:在原数列的第i个元素后面添加一个新元素k;如果原数列的第i个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子)
  • MIN_GAP:查询相邻两个元素的之间差值(绝对值)的最小值
  • MIN_SORT_GAP:查询所有元素中最接近的两个元素的差值(绝对值)

 

例如一开始的序列为

 

执行操作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命令,输出一行答案即可。

 

输入输出样例

输入样例#1:
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
输出样例#1:
2
2
1

说明

对于30%的数据,N≤1,000, M≤5,000

对于100%的数据, N,M≤500,000

对于所有的数据,序列内的整数不超过 \(5 \times 10^8\)。

时限2s

 

   这个题看似是要维护一串数列,实际上只需要一部分信息,稍加处理就完成了这一题的工作。在不用维护排名的情况下,splay写起来很方便,这个题为了方便,并考虑到常数问题,开了一个set。事实上如果对splay开两个root,效果是相同的,只是会有点乱。

 

   我们来看INSERT操作,因为INSERT是要插入原数列(很重要!就是因为看错了这一点我才写挂的。。。)中第i个数后面,那么我们在初始状态下认为每一个数属于一组(类似链),每次插入前需要的是当前组最后一个和下一组第一个(第n组没有下一组),来维护MIN_GAP,也就是相邻元素之间的差值,把它放到splay里去维护。我们不仅要插入这些“差值”,而且还要删除,因为插入一个元素之后,原来相邻的元素可能不再相邻,比如这样:

   我们如果在5和6之间插入8,那么原来存在的一个差值1会消失,因为不排除在其他区段会有1这样的差值,所以通过splay或set删掉一个1。我们认为5在前面一段,且是前面一段的最后一个,不然8不可能被添加到5的后面去,那么6是后面一段的第一个。此时将5到8的差值3插入,更新前一段的最后一个元素为8,再把6到8的差值2插入。

 

   这样我们就维护了MIN_GAP,也就是相邻元素的最小绝对差值。

 

   那么如何维护MIN_SORT_GAP(任意两个元素的最小绝对差值)呢?

 

   我们还有一个set,可以帮助我们查找二叉排序树中元素所在的地址。我们在进行INSERT操作后,也要把这个元素加到set里面去,注意这里是multiset,我们用count查询该元素出现的次数,如果次数>1,那么MIN_SORT_GAP就是0,且不会再更新到更小了。如果不是0,那么用迭代器访问新插入元素的前驱和后继,更新MIN_SORT_GAP为最近两个元素差值与自己的最小值。

 

   这个题是练习splay的一道基础好题。

 

Code:

#include<cstdio>
#include<cstring>
#include<set>
using std::multiset;
multiset<int> s;//这棵树维护元素
int min(int x,int y)
{
    return x<y?x:y;
}
int abs(int x)
{
    if(x<0)
        return -x;
    return x;
}
struct node//这棵树维护区间差值
{
    int key,num;
    node *s[2];
    node(int key)
    {
        this->key=key;
        num=1;
        s[0]=NULL;
        s[1]=NULL;
    }
    node()
    {
        s[0]=NULL;
        s[1]=NULL;
    }
    int getd(int x)//查找下一步应该去往哪个方向 如果找到了返回-1
    {
        if(key==x)
            return -1;
        return x>key;
    }
};
node *root=NULL;
void Rotate(node *&rt,int d)
{
    node *tmp=rt->s[d];
    rt->s[d]=tmp->s[d^1];
    tmp->s[d^1]=rt;
    rt=tmp;
    return;
}
void splay(node *&rt,int x)
{
    int d1=rt->getd(x);
    if(d1==-1)
        return;
    int d2=rt->s[d1]->getd(x);
    if(d2==-1)
    {
        Rotate(rt,d1);
        return;
    }
    splay(rt->s[d1]->s[d2],x);
    if(d1==d2)
    {
        Rotate(rt,d1);
        Rotate(rt,d1);
        return;
    }
    else
    {
        Rotate(rt->s[d1],d2);
        Rotate(rt,d1);
        return;
    }
}
void Insert(node *&rt,int x)
{
    if(!rt)
    {
        rt=new node(x);
        return;
    }
    int d=rt->getd(x);
    if(d==-1)
    {
        rt->num++;
        return;
    }
    Insert(rt->s[d],x);
    return;
}
int getm(node *&rt,int d)//找最大/最小值
{
    if(!rt->s[d])
        return rt->key;
    return getm(rt->s[d],d);
}
void Delete(node *&rt,int x)
{
    int d=rt->getd(x);
    if(d==-1)
    {
        if(rt->num>1)
        {
            rt->num--;
            return;
        }
        if(!rt->s[0]&&!rt->s[1])
        {
            rt=NULL;
            return;
        }

        if(rt->s[0])
        {
            int k=getm(rt->s[0],1);
            splay(rt->s[0],k);
            rt->s[0]->s[1]=rt->s[1];
            rt=rt->s[0];
            return;
        }
        else
        {
            int k=getm(rt->s[1],0);
            splay(rt->s[1],k);
            rt->s[1]->s[0]=rt->s[0];
            rt=rt->s[1];
            return;
        }
    }
    Delete(rt->s[d],x);
    return;
}
int seg[510000],st[510000],ed[510000];
int main()
{
    int n,m,u,v;
    int minn=999999999;
    scanf("%d%d",&n,&m);
    multiset<int>::iterator it;//迭代器
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&u);
        st[i]=u;
        ed[i]=u;
        s.insert(u);
        if(i>1)
        {
            Insert(root,abs(u-ed[i-1]));
            it=s.find(u);
            it++;
            if(it!=s.end())
                minn=min(minn,abs(*it-u));
            it--;
            it--;
            if(it!=s.end())
                minn=min(minn,abs(*it-u));
        }
    }
    char c[50];

    for(int i=1;i<=m;i++)
    {
        scanf("%s",c);
        if(c[0]=='I')
        {
            scanf("%d%d",&u,&v);
            if(u!=n)
                Delete(root,abs(st[u+1]-ed[u]));//原来的尾与首要断开
            Insert(root,abs(v-ed[u]));//更新新的尾与尾、尾与首
            if(u!=n)
                Insert(root,abs(st[u+1]-v));
            s.insert(v);
            if(s.count(v)>1||minn==0)//minn为0不必更新
                minn=0;
            else
            {
                it=s.find(v);
                it++;
                if(it!=s.end())
                    minn=min(minn,*it-v);
                it--;
                it--;
                if(it!=s.end())
                    minn=min(minn,v-*it);
            }
            ed[u]=v;
        }
        else
        {
            if(c[4]=='S')
                printf("%d\n",minn);
            else
                printf("%d\n",getm(root,0));
        }
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */