Luogu P1110 [ZJOI2007]报表统计 题解

#include<bits/stdc++.h>
#define It multiset<int>::iterator
#define inf 2000000010//inf不要太小哦
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x<10) putchar(x+'0');
else write(x/10),putchar(x%10+'0');
}
int n,m,Min=inf,las,nxt,tmp,a[500010],b[500010];//a,b分别表示每一段的开头与结尾
multiset<int> v,d;//v表示全部,d表示相邻
char c;
int main(){
n=read();m=read();
for(int i=1;i<=n;i++) a[i]=b[i]=read(),v.insert(a[i]);
v.insert(inf);v.insert(-inf);//防止奇怪错误
for(int i:v) Min=min(Min,abs(i-las)),las=i;//预处理开始的情况
for(int i=2;i<=n;i++) d.insert(abs(a[i]-a[i-1]));//预处理插入相邻之差
for(int x,y,i=1;i<=m;i++){
c=getchar();while(c!='M'&&c!='I'&&c!='N'&&c!='_'&&c!='S'&&c!='O'&&c!='T'&&c!='G'&&c!='A'&&c!='P'&&c!='E'&&c!='R') c=getchar();
if(c=='I'){
while(c=='M'c=='I'c=='N'c=='_'c=='S'c=='O'c=='T'c=='G'c=='A'c=='P'c=='E'c=='R') c=getchar();
x=read();y=read();
las=b[x];
if(x!=n){
nxt=a[x+1];
tmp=abs(las-nxt);//如果插入一个数必定把前一个数与后一个数隔开，所以要删去
d.erase(d.find(tmp));
d.insert(abs(y-nxt));//插入新的后继
}
d.insert(abs(y-las));//插入新的前驱
b[x]=y;
It pos=v.lower_bound(y);//寻找后继
Min=min(Min,abs(y-*pos));
--pos;//后继-1就是前驱
Min=min(Min,abs(y-*pos));
v.insert(y);//插入总
}else{
c=getchar();c=getchar();c=getchar();c=getchar();
if(c=='G'){
while(c=='M'c=='I'c=='N'c=='_'c=='S'c=='O'c=='T'c=='G'c=='A'c=='P'c=='E'c=='R') c=getchar();
write(*d.begin());putchar('\n');//输出最小值
}else{
while(c=='M'c=='I'c=='N'c=='_'c=='S'c=='O'c=='T'c=='G'c=='A'c=='P'c=='E'c=='R') c=getchar();
write(Min);putchar('\n');//输出最小值
}
}
}
}