题目描述
维护一个初始长度为 $n$ 的非负整数序列，支持一下三种操作：
- 在初始第 $i$ 个整数后面插入一个整数，若初始第 $i$ 个整数后面已经插入过其它整数，则将该整数插入到这些整数的最后面。
- 查询整个序列中相邻两个元素之间差值的最小值。
- 查询整个序列中任意两个元素之间差值的最小值。
$n,m\le 500000$，序列内的整数不超过 $5\times 10^8$。
算法分析
水题我都不会写。。。
对于每个初始整数及它后面插入的数放在一起维护，记录每段左右两端的值，由于相邻两个元素可能会变化，因此使用可重集合维护，第二种询问维护序列中所有整数的集合，在每次插入时直接二分与它最接近的两个整数更新答案即可。
时间复杂度为 $O(nlog_2n)$，卡常数。
代码实现
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
| #include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <algorithm>
#define N 500005
std::set<int> s;std::map<int,int> mp;int lval[N],rval[N],minsortgap=0x3f3f3f3f;
inline void gap_insert(int x) {
if(mp.find(x)==mp.end()) mp[x]=1;
else ++mp[x];
}
inline void gap_erase(int x) {if(!(--mp[x])) mp.erase(mp.find(x));}
inline void sortgap_insert(int x) {
std::set<int>::iterator it=s.lower_bound(x),is=s.upper_bound(x);
if(it!=s.end()) minsortgap=std::min(minsortgap,*it-x);
if(is!=s.begin()) minsortgap=std::min(minsortgap,x-*(--is));
s.insert(x);
}
int main() {
int n,m;scanf("%d%d",&n,&m);
for(register int i=1;i<=n;++i) {
int x;scanf("%d",&x);lval[i]=rval[i]=x;
if(i-1) gap_insert(abs(lval[i]-rval[i-1]));
sortgap_insert(x);
}
while(m--) {
char opt[100];scanf("%s",opt);
if(opt[0]=='I') {
int i,k;scanf("%d%d",&i,&k);
if(i+1<=n) {
gap_erase(abs(lval[i+1]-rval[i]));
gap_insert(abs(lval[i+1]-k));
}
gap_insert(abs(k-rval[i]));rval[i]=k;sortgap_insert(k);
}
else if(opt[4]=='G') printf("%d\n",mp.begin()->first);
else printf("%d\n",minsortgap);
}
return 0;
}
|