Describe
小 Q 的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小 Q 希望可以帮妈妈分担一些工作，作为她的生日礼物之一。
经过仔细观察，小 Q 发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。
在最开始的时候，有一个长度为$ n$的整数序列$a$，并且有以下三种操作：
INSERT i k：在原数列的第$ i$个元素后面添加一个新元素$ k$；如果原数列的第$ i$个元素已经添加了若干元素，则添加在这些元素的最后（见样例说明）。MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值。MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）。
于是小 Q 写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
Solution
开两个multiset即可。
一个存放所有元素的最小差值，一个存放相邻元素的最小差值。
每次插入一个数字可以处理下前驱和后继即可。
细节详见代码。
P.S.千万不要作死用vector.
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#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');//输出最小值 } } } } |
