NC20600. [ZJOI2007]报表统计
描述
输入描述
第一行包含两个整数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
输出:
2 2 1
说明:
一开始的序列为{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。
C++(g++ 7.5.0) 解法, 执行用时: 2320ms, 内存消耗: 80200K, 提交时间: 2023-05-15 21:47:33
# include<iostream>
# include<set>
# include<cmath>
# include<algorithm>
using namespace std;
const int maxn=5e5+1e2;
const int INF=0x3f3f3f3f;
multiset<int> delta,full;
int st[maxn],ed[maxn];
int srt=INF;
void update_srt(int x){
multiset<int>::iterator it = full.lower_bound(x);
int nw = *it - x;
--it;
nw = min( nw , x - *it );
srt = min( srt , nw );
full.insert(x);
}
int main()
{
int n, m;
cin>>n>>m;
int temp;
// 初始化st和ed, full和delta
for(int i=1;i<=n;i++){
cin>>temp;
st[i] = temp;
ed[i] = temp;
if (i>1){
delta.insert(abs(st[i]-ed[i-1]));
}
}
full.insert(INF),
full.insert(-INF);
for(int i=1;i<=n;i++){
update_srt(st[i]);
}
char op[100];
int x, k;
for(int i=0;i<m;i++){
scanf("%s", op);
if(op[0] == 'I'){
cin>>x>>k;
// 注意要删除掉原来的
delta.erase(delta.find(abs(st[x+1]-ed[x]))),
// 加入新的delta
delta.insert(abs(ed[x]-k));
delta.insert(abs(st[x+1]-k));
ed[x] = k;
// 更新full
update_srt(k);
}
if(op[4]=='G'){
cout<<*delta.begin()<<endl;
}
if(op[4]=='S'){
cout<<srt<<endl;
}
}
}
C++(clang++11) 解法, 执行用时: 2708ms, 内存消耗: 80092K, 提交时间: 2021-05-16 11:00:42
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
const int M=500000+1000;
const int inf=0x3f3f3f3f;
inline int read(){
int x=0,k=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*k;
}
multiset<int>S,G;
int st[M],ed[M],m,n,ans=inf;
void update_sort(int x)
{
multiset<int>::iterator it=S.lower_bound(x);
int now=*it-x;
it--;
now=min(now,x-*it);
ans=min(ans,now);
S.insert(x);
return ;
}
void update_gap(int pos,int num)
{
G.insert(abs(ed[pos]-num));
if(pos!=n)
{
G.erase(G.find(abs(ed[pos]-st[pos+1])));
G.insert(abs(st[pos+1]-num));
}
ed[pos]=num;
return ;
}
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++) st[i]=ed[i]=read();
S.insert(-inf);
S.insert(inf);
for(int i=1;i<n;i++) G.insert(abs(st[i+1]-ed[i]));
for(int i=1;i<=n;i++) update_sort(st[i]);
while(m--)
{
char s[20];
int pos,num;
scanf("%s",s);
if(s[4]=='S') printf("%d\n",ans);
if(s[4]=='G') printf("%d\n",*G.begin());
if(s[0]=='I')
{
scanf("%d%d",&pos,&num);
update_sort(num);
update_gap(pos,num);
}
}
}
C++14(g++5.4) 解法, 执行用时: 2304ms, 内存消耗: 66064K, 提交时间: 2020-01-30 13:41:52
#include<bits/stdc++.h>
using namespace std;
const int MX=5e5+9;
const int inf=0x3f3f3f3f;
multiset<int> full,delta;
int n,m,x,st[MX],ed[MX],mi=inf,pos;
char s[MX];
void que_mi(int x){
multiset<int>::iterator it;
it=full.upper_bound(x);
mi=min(mi,abs(*it-x));
it--;
mi=min(mi,abs(*it-x));
full.insert(x);
}
void que_detal(int pos,int x){
int nw=abs(x-ed[pos]);
delta.insert(nw);
if( pos!=n ){
delta.insert(abs(st[pos+1]-x));
delta.erase(delta.find(abs(st[pos+1]-ed[pos])));
}
ed[pos]=x;
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d %d",&n,&m);
for( int i=1 ; i<=n ; i++ ){
scanf("%d",&x);
st[i]=ed[i]=x;
}
full.insert(inf);
full.insert(-inf);
for( int i=1 ; i<=n ; i++ )
que_mi(st[i]);
for( int i=2 ; i<=n ; i++ )
delta.insert(abs(st[i]-ed[i-1]));
while( m-- ){
scanf("%s",s);
if( s[0]=='I' ){
scanf("%d %d",&pos,&x);
if( mi!=0 )
que_mi(x);
que_detal(pos,x);
}
else if( s[4]=='G' )
printf("%d\n",*delta.begin());
else
printf("%d\n",mi);
}
return 0;
}