[ZJOI2007] 报表统计

题目

小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写了一个程序,使得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?

INPUT

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

OUTPUT

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

SAMPLE

INPUT

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

OUTPUT

2
2
1

数据规模

对于30%的数据,N≤ 1000 , M ≤ 5000
对于100%的数据,N , M ≤500000
对于所有的数据,序列内的整数不超过5×10^8。

解题报告

考试题的加强版,数据大了十倍
考试打了个暴力,骗了20分= =
正解:
STL三件套——vec,que,还有set
vector用来存每个位置后面加的元素
priority_queue用来存相邻的差值,要用两个,一个存答案,一个用来垃圾回收(为什么要垃圾回收?当我们插入一个数时,我们将两个原本相连的数分开了,那么他们不再相连,所以我们要清理掉它)
set用来处理全局最小差,我们可以用set找到一个数的前驱与后驱,而且显然的是,最小差一定存在于排完序后的相邻的数,所以我们可以进行预处理,边插入边更新
 #include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
using namespace std;
inline int read(){
int sum(),f();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar())
if(ch=='-')
f=-;
for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());
return sum*f;
}
priority_queue<int,vector<int>,greater<int> >dust;
priority_queue<int,vector<int>,greater<int> >ans1;
vector<int>v[];
multiset<int>st;
multiset<int>::iterator it;
int n,m;
int w[];
int ans2(0x7fffffff);
char op[];
inline int my_max(int a,int b){
return a>b?a:b;
}
inline int my_min(int a,int b){
return a<b?a:b;
}
inline int jdz(int x){
return x>=?x:-x;
}
inline void insert(int x,int y){
int size(v[x].size());
if(x<n)
dust.push(jdz(v[x][size-]-v[x+][]));
ans1.push(jdz(y-v[x][size-]));
if(x<n)
ans1.push(jdz(y-v[x+][]));
v[x].push_back(y);
st.insert(y);
it=st.find(y);
if(it!=st.begin()){
it--;
int tmp(*it);
ans2=my_min(jdz(y-tmp),ans2);
it++;
}
if(it!=st.end()){
it++;
int tmp(*it);
ans2=my_min(jdz(y-tmp),ans2);
}
}
inline int query(){
while(){
if(dust.empty()||dust.top()!=ans1.top())
break;
dust.pop();
ans1.pop();
}
return ans1.top();
}
int main(){
freopen("form.in","r",stdin);
freopen("form.out","w",stdout);
n=read(),m=read();
for(int i=;i<=n;i++){
w[i]=read();
st.insert(w[i]);
it=st.find(w[i]);
if(it!=st.begin()){
it--;
int tmp(*it);
ans2=my_min(ans2,jdz(tmp-w[i]));
it++;
}
if(it!=st.end()){
it++;
int tmp(*it);//cout<<tmp<<endl;
ans2=my_min(ans2,jdz(tmp-w[i]));
}
if(i^)
ans1.push(jdz(w[i]-w[i-]));
v[i].push_back(w[i]);
// cout<<i<<' '<<w[i]<<' '<<ans2<<endl;
}
while(m--){
scanf("%s",op);
if(op[]=='I'){
int x(read()),y(read());
insert(x,y);
}
else{
if(strlen(op)<)
printf("%d\n",query());
else
printf("%d\n",ans2);
}
}
}
好强大的STL啊= =

最新文章

  1. 浅析C# new和override的区别
  2. import的用法
  3. 结构类模式(四):装饰(Decorator)
  4. 【转】二叉树 VS hashtable
  5. bing---iis how to process http request
  6. Oracle_OCP课程实验学习
  7. MD5加密解密
  8. Knockout应用开发指南 第七章:Mapping插件
  9. VS2010程序打包操作
  10. Java文件流之练习
  11. pythonのsimple_tag
  12. elixir mix 简介
  13. obspy下载地震波数据
  14. Problem A: 编写函数:三个数的最大最小值
  15. TStrings与Memo.Lines赋值的问题
  16. Spring Security OAuth2实现单点登录
  17. Linux内核分析作业第三周
  18. 电容充放电时间常数RC计算方法
  19. MySQL 数据库定时自动备份
  20. 什么是Asp.net Core?和 .net core有什么区别?(转)

热门文章

  1. Silverlight将Excel导入到SQLserver数据库
  2. Oracle数据库web维护客户端管理工具软件
  3. python爬虫从入门到放弃前奏之学习方法
  4. H5个性三级联动日期插件(一)
  5. JAVAEE——spring02:使用注解配置spring、sts插件、junit整合测试和aop演示
  6. Linux下如何启动svn服务器
  7. shell中source与sh区别
  8. Python Click 学习笔记(转)
  9. socket编程 做一回文抄公
  10. [leetcode-566-Reshape the Matrix]