[ZJOI2007]报表统计(splay,堆)
2024-09-04 21:38:49
Description
题目描述
Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一。
经过仔细观察,小Q发现统计一张报表实际上是维护一个非负整数数列,并且进行一些查询操作。
在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作:
INSERT i k
:在原数列的第i个元素后面添加一个新元素kk;如果原数列的第ii个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子)MIN_GAP
:查询相邻两个元素的之间差值(绝对值)的最小值MIN_SORT_GAP
:查询所有元素中最接近的两个元素的差值(绝对值)
例如一开始的序列为5, 3, 15,3,1。
执行操作INSERT 2 9
将得到:5, 3, 9, 15,3,9,1,此时MIN_GAP
为22,MIN_SORT_GAP
为22。
再执行操作INSERT 2 6
将得到:5, 3, 9, 6, 15,3,9,6,1
注意这个时候原序列的第22个元素后面已经添加了一个99,此时添加的66应加在99的后面。这个时候MIN_GAP
为22,MIN_SORT_GAP
为11。
于是小Q写了一个程序,使得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?
输入格式
第一行包含两个整数NN,MM,分别表示原数列的长度以及操作的次数。
第二行为NN个整数,为初始序列。
接下来的MM行每行一个操作,即INSERT i k
,MIN_GAP
,MIN_SORT_GAP
中的一种(无多余空格或者空行)。
输出格式
对于每一个MIN_GAP
和MIN_SORT_GAP
命令,输出一行答案即可。
Solution
用平衡树维护MIN_SORT_GAP,用堆维护MIN_GAP
Code
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e6+;
int ch[N][],fa[N],val[N],rt,tot,n,m,a[N],b[N],ans=<<,pos,k;
char s[];
priority_queue <int,vector<int>,greater<int> > q1,q2;
int get(int x)
{
return x==ch[fa[x]][];
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int wh=get(x);
fa[ch[x][wh^]]=y;
ch[y][wh]=ch[x][wh^];
ch[x][wh^]=y;
fa[x]=z,fa[y]=x;
if(z) ch[z][y==ch[z][]]=x;
}
void splay(int x)
{
for(int f=fa[x];f=fa[x],f;rotate(x))
if(fa[f]) rotate(get(f)==get(x)?f:x);
rt=x;
}
int pre()
{
int now=ch[rt][];
while(ch[now][]) now=ch[now][];
return now;
}
int nxt()
{
int now=ch[rt][];
while(ch[now][]) now=ch[now][];
return now;
}
void change()
{
if(ch[rt][]) ans=min(ans,abs(val[rt]-val[pre()]));
if(ch[rt][]) ans=min(ans,abs(val[rt]-val[nxt()]));
}
void insert(int x)
{
if(!rt)
{
rt=++tot,val[tot]=x;
return;
}
int now=rt,pre=;
while()
{
if(x==val[now])
{
ans=;
return ;
}
pre=now,now=ch[pre][x>val[pre]];
if(!now)
{
ch[pre][x>val[pre]]=++tot;
fa[tot]=pre,val[tot]=x;
splay(tot);
return ;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
if(ans>) insert(a[i]);
if(ans>) change();
if(i>) q1.push(abs(a[i]-a[i-]));
}
while(m--)
{
scanf("%s",s);
if(s[]=='M')
{
if(s[]=='G')
{
while(!q2.empty() && q2.top()==q1.top())
q1.pop(),q2.pop();
printf("%d\n",q1.top());
}
else printf("%d\n",ans);
}
else
{
scanf("%d%d",&pos,&k);
if(ans>) insert(k);
if(ans>) change();
if(pos<n)
{
q2.push(abs(b[pos]-a[pos+]));
q1.push(abs(k-a[pos+]));
}
q1.push(abs(b[pos]-k));
b[pos]=k;
}
}
return ;
}
最新文章
- 特性 Attribute
- NOIP2004火星人
- 基于AWS的云服务架构最佳实践
- windows上在linux客户端上传小文件lrzsz
- slogan
- Lambda表达式的本质是匿名函数
- [SQL Server系] -- 基本概念
- BZOJ 3265 志愿者招募增强版 单
- 原生JavaScript拖动div兼容多种浏览器
- Unix/Linux环境C编程入门教程(11) 开发环境搭建VMWare虚拟安装之虚拟化检测
- Unity5系列资源管理AssetBundle——打包
- c语言基础编程
- Linux 通过端口转发来访问内网服务
- 腾讯Java程序员第二轮面试11个问题,你会几个?
- PHP获取一周的日期
- Vue深度学习(2)
- .NET Core微服务之基于Steeltoe集成Zuul实现统一API网关
- 51nod 1405 树的距离之和 树形dp
- Unity中对系统类进行扩展的方法
- mac下安装redis详细步骤