洛谷 P1110 [ZJOI2007]报表统计 题解【splay】【set】
点击量：158
一道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 55 3 1INSERT 2 9MIN_SORT_GAPINSERT 2 6MIN_GAPMIN_SORT_GAP输出样例#1：221说明
对于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;
}
说点什么